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

Question

在算法中,每当我添加一个值时,我都必须计算数据集的第75个百分位数.现在我这样做:

1. 获得价值 x
2. x在后面插入已排序的数组
3. 交换x,直到数组排序
4. 读取位置处的元素 array[array.size * 3/4]

点3是O(n),其余是O(1),但这仍然很慢,特别是如果阵列变大.有没有办法优化这个？

UPDATE

谢谢尼基塔!由于我使用的是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

你可以用两堆来做.不确定是否有一个不太"设计"的解决方案,但是这个解决方案提供了O(logn)时间复杂性,并且堆也包含在大多数编程语言的标准库中.

第一个堆(堆A)包含最小的75%元素,另一个堆(堆B) - 其余(最大25%).第一个是最重要的元素,第二个是最小元素.

1. 添加元素.

看看新元素x是否<= max(A).如果是,请将其添加到堆中A,否则 - 添加到堆中B.
现在,如果我们添加x到堆A并且它变得太大(占据超过75%的元素),我们需要从A(O(logn))中删除最大元素并将其添加到堆B(也是O(logn)).
类似的,如果堆B变得太大了.

2. 找到"0.75中位数"

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

编辑
正如Dolphin所说,我们需要精确指定每个堆应该有多大(如果我们想要精确答案).例如,如果size(A) = floor(n * 0.75)和size(B)是休息,然后,每一个n > 0,array[array.size * 3/4] = min(B).

Answer 2

一个简单的订单统计树就足够了.

此树的平衡版本支持O(logn)时间插入/删除和Rank访问.因此,您不仅可以获得75%的百分位数,而且可以获得66%或50%或任何您需要的内容,而无需更改代码.

如果频繁访问75%百分位数,但只插入频率较低,则可以在插入/删除操作期间始终缓存75%百分位元素.

大多数标准实现(如Java的TreeMap)都是订单统计树.