增量计算与提前计算

增量计算与提前计算

增量计算是指仅对变化的数据部分进行处理，而非重新计算整个数据集。

提前计算（也称为预计算）则是在运行时需求出现之前预先计算并存储结果，以避免在关键路径上进行实时计算。预计算在C++这种编译型语言也叫编译期计算，通过const派系的特性、TMP技术可以实现，在基础部分有提到多种方法实现。

这两种计算模式常常结合使用：提前计算静态或半静态数据，增量计算动态变化数据。

增量计算的最常见的场景就是移动平均数、中位数、最大值、最小值等指标的计算。

实现增量计算的关键在于高效的数据结构选择和变化跟踪机制。

#include <deque>
#include <iostream>
#include <set>
#include <vector>

class DataStatistics {
 private:
  std::deque<int> window;
  int maxSize;
  long long sum;

  std::deque<int> maxDeque;  // 用于滑动窗口的最大值
  std::deque<int> minDeque;  // 用于滑动窗口的最小值

  // 用于中位数计算 - 使用multiset维护有序状态
  std::multiset<int> lowerHalf;  // 最大堆（使用反向迭代器）
  std::multiset<int> upperHalf;  // 最小堆

 public:
  DataStatistics(int size) : maxSize(size), sum(0) {}

  void addData(int value) {
    if (maxSize == 0) {
      return;
    }

    if (window.size() >= maxSize) {
      removeOldest();
    }

    window.push_back(value);
    sum += value;

    while (!maxDeque.empty() && maxDeque.back() < value) {
      maxDeque.pop_back();
    }
    maxDeque.push_back(value);

    while (!minDeque.empty() && minDeque.back() > value) {
      minDeque.pop_back();
    }
    minDeque.push_back(value);

    addToMedianStructure(value);
  }

  double getMovingAverage() {
    if (window.empty()) return 0.0;
    return static_cast<double>(sum) / window.size();
  }

  int getMax() {
    if (window.empty()) return 0;
    return maxDeque.front();
  }

  int getMin() {
    if (window.empty()) return 0;
    return minDeque.front();
  }

  double getMedian() {
    if (window.empty()) return 0.0;

    if (lowerHalf.size() == upperHalf.size()) {
      if (lowerHalf.empty()) return 0.0;
      return (*lowerHalf.rbegin() + *upperHalf.begin()) / 2.0;
    } else {
      return *lowerHalf.rbegin();
    }
  }

  int getCurrentSize() { return window.size(); }

  std::vector<int> getData() {
    return std::vector<int>(window.begin(), window.end());
  }

 private:
  void removeOldest() {
    if (window.empty()) return;

    int oldestValue = window.front();
    sum -= oldestValue;
    window.pop_front();

    if (!maxDeque.empty() && maxDeque.front() == oldestValue) {
      maxDeque.pop_front();
    }
    if (!minDeque.empty() && minDeque.front() == oldestValue) {
      minDeque.pop_front();
    }

    removeFromMedianStructure(oldestValue);
  }

  void addToMedianStructure(int value) {
    if (lowerHalf.empty() || value <= *lowerHalf.rbegin()) {
      lowerHalf.insert(value);
    } else {
      upperHalf.insert(value);
    }

    balanceHeaps();
  }

  void removeFromMedianStructure(int value) {
    auto it_lower = lowerHalf.find(value);
    if (it_lower != lowerHalf.end()) {
      lowerHalf.erase(it_lower);
    } else {
      auto it_upper = upperHalf.find(value);
      if (it_upper != upperHalf.end()) {
        upperHalf.erase(it_upper);
      }
    }

    balanceHeaps();
  }

  void balanceHeaps() {
    // 确保lowerHalf的大小要么与upperHalf相同，要么比它多一个
    if (lowerHalf.size() > upperHalf.size() + 1) {
      int moved = *lowerHalf.rbegin();
      lowerHalf.erase(std::prev(lowerHalf.end()));
      upperHalf.insert(moved);
    } else if (upperHalf.size() > lowerHalf.size()) {
      int moved = *upperHalf.begin();
      upperHalf.erase(upperHalf.begin());
      lowerHalf.insert(moved);
    }
  }
};