34

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

  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;
};
4

6 回答 6

36

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

第一个堆（堆 A）包含最小的 75% 元素，另一个堆（堆 B）- 其余的（最大的 25%）。第一个在顶部有最大的元素，第二个 - 最小的。

  1. 添加元素。

查看新元素x是否为 <= max(A)。如果是，则将其添加到 heap A，否则 - 添加到 heap 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[array.size * 3/4] = min(B)。

于 2010-09-17T19:44:25.417 回答
16

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

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

如果您经常访问 75% 的百分位，但插入的频率较低，则您始终可以在插入/删除操作期间缓存 75% 的百分位元素。

大多数标准实现（如 Java 的 TreeMap）都是顺序统计树。

于 2010-09-17T23:05:46.870 回答
3

如果您可以使用近似答案，则可以使用直方图而不是将整个值保存在内存中。

对于每个新值，将其添加到相应的 bin。通过遍历 bin 和求和计数来计算第 75 个百分位数，直到达到人口规模的 75%。百分位值介于 bin （您停在）下限和上限之间。

这将提供 O(B) 复杂度，其中 B 是 bin 的计数，即range_size/bin_size. （使用bin_size适合您的用户案例）。

我已经在 J​​VM 库中实现了这个逻辑：https ://github.com/IBM/HBPE ，您可以将其用作参考。

于 2020-05-06T09:13:40.750 回答
-2

如果您有一组已知的值，以下将非常快：

创建一个大型整数数组（偶数字节也可以），其元素数等于数据的最大值。例如，如果 t 的最大值为 100,000，则创建一个数组

int[] index = new int[100000]; // 400kb

现在遍历整个值集，如

for each (int t : set_of_values) {
  index[t]++;
}

// You can do a try catch on ArrayOutOfBounds just in case :)

现在计算百分位数为

int sum = 0, i = 0;
while (sum < 0.9*set_of_values.length) {
  sum += index[i++];
}

return i;

如果值不符合这些限制，您也可以考虑使用 TreeMap 而不是数组。

于 2012-09-24T11:48:02.380 回答
-2

您可以使用二进制搜索在 O(log n) 中找到正确的位置。但是，将数组向上移动仍然是 O(n)。

于 2010-09-17T19:29:17.190 回答
-2

这是一个 JavaScript 解决方案。将其复制粘贴到浏览器控制台中即可。$scores包含分数列表，并$percentile给出n-th percentile列表的。所以第 75 个百分位是 76.8，第 99 个百分位是 87.9。

function get_percentile($percentile, $array) {
    $array = $array.sort();
    $index = ($percentile/100) * $array.length;
    if (Math.floor($index) === $index) {
         $result = ($array[$index-1] + $array[$index])/2;
    }
    else {
        $result = $array[Math.floor($index)];
    }
    return $result;
}

$scores = [22.3, 32.4, 12.1, 54.6, 76.8, 87.3, 54.6, 45.5, 87.9];

get_percentile(75, $scores);
get_percentile(90, $scores);
于 2016-02-03T06:58:13.080 回答