给定数百万个数字流，如何近似计算第 90 个百分位数

Question

我需要计算每秒获得的数字流的第 90 个百分位数。它可能高达每秒数百万个数字，但第 90 个百分位数只需要近似，不一定准确。优先队列/最大堆是执行此操作的最佳方法还是其他方法？如果是这样，我最终将如何估算该值？

Answer 1

您选择的方法将取决于您的数据的性质。如果您知道，在开始接收项目流之前，您将收到多少项目，您可以使用基于堆的选择算法。例如，如果您知道您将收到 1,000,000 件商品并且您需要知道 90% 的百分位数，那么您就知道第 100,000 件商品标志着第 90 个百分位数。要找到它，请执行以下操作：

create an empty min heap
add the first 100,000 items to the heap
for each remaining item
    if the item is larger than the smallest item on the heap
        remove the smallest item from the heap
        add the new item to the heap

完成后，堆包含 100,000 个最大的项目，而堆的根是其中最小的。这是您的第 90 个百分位值。

一种使用更多内存的更快方法是将所有传入项目保存在一个列表中，然后运行Quickselect以查找第 100,000 个最大的项目。

以上两点都会给你一个准确的答案。

如果您知道您的数字将在某个相对较小的范围内，您可以创建存储它们的存储桶。例如，您说您的数字在 0 到 150 的范围内。因此您需要 151 个存储桶。您的值不是整数，但由于您说近似值很好，您可以在将它们放入桶之前对这些值进行四舍五入。所以这样的事情应该有效：

buckets = array of 151 values
for each value
    int_value = round(value)
    buckets[int_value] = buckets[int_value] + 1

既然您对每个值进行了计数，找出第 90 个百分位数就是从数组末尾（最高值）计数值直到达到 10% 的简单问题。就像是：

target = 100000  // we want the top 10 percent
bucket = 150
total = 0
while (bucket >= 0)
    total += buckets[bucket]
    if (total >= target)
        break
    bucket = bucket - 1

此时， 的值bucket是您大约 90 个百分位的值。

这种方法将比其他两种方法更快，并且使用的内存要少得多。但它是一个近似值，而不是一个精确值。