algorithm - 重复计算百分位数的快速算法？

Question

在算法中我必须计算 75th percentile每当我添加一个值时，数据集的。现在我正在这样做:

1. 获取值x
2. 将x插入到一个已经排好序的数组的后面
3. 向下交换 x 直到数组排序完毕
4. 读取 array[array.size * 3/4] 位置的元素

点 3 是 O(n)，其余是 O(1)，但这仍然很慢，尤其是当数组变大时。有什么办法可以优化吗？

更新

谢谢尼基塔!因为我使用的是 C++，所以这是最容易实现的解决方案。这是代码:

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() > size_lower) {
      // lower to upper
      std::pop_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.push_back(_lower.back());
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.pop_back();
    } else if (_lower.size() < size_lower) {
      // upper to lower
      std::pop_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.push_back(_upper.back());
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.pop_back();
    }            
  }

  /// Access the percentile in O(1)
  const T& get() const {
    return _lower.front();
  }

  void clear() {
    _lower.clear();
    _upper.clear();
  }

private:
  double _percentile;
  std::vector<T> _lower;
  std::vector<T> _upper;
};

Answer 1

你可以用两个 heaps .不确定是否有更“人为”的解决方案，但这个解决方案提供了 O(logn) 时间复杂度，并且堆也包含在大多数编程语言的标准库中。

第一个堆(堆 A)包含最小的 75% 元素，另一个堆(堆 B)- 其余(最大的 25%)。第一个元素最大，第二个元素最小。

1. 添加元素。

查看新元素 x 是否为 <= max(A)。如果是，将其添加到堆A，否则-添加到堆B。
现在，如果我们将 x 添加到堆 A 并且它变得太大(包含超过 75% 的元素)，我们需要从 A 中移除最大的元素(O(logn )) 并将其添加到堆 B(也是 O(logn))。
如果堆 B 变得太大，则类似。

1. 找到“0.75 中位数”

只取 A 中的最大元素(或 B 中的最小元素)。需要 O(logn) 或 O(1) 时间，具体取决于堆实现。

编辑
正如 Dolphin 指出的那样，我们需要为每个 n 精确指定每个堆的大小(如果我们想要精确的答案)。例如，如果 size(A) = floor(n * 0.75) 和 size(B) 是其余部分，则对于每个 n > 0, 数组[array.size * 3/4] = min(B)。