获得数据流的平均值,p95和p99

Question

我有传入的数据,我想计算该数据的平均值,第95和第99百分位数 - 我对最后1000个值最感兴趣.在任何时候,我都想查询这个对象以获得三个值中的任何一个(这可以在任何时候发生,而不仅仅是当看到mod 1000的数字是0时).有没有办法在不保留最后1000个样本的情况下获得这三个值？

这不一定是完美的,所以我们可以使用一些技巧来获得一个很好的估计.此外,速度是另一个问题.谢谢

(我将在C++中这样做,但我认为这并不重要)

Answer 1

至少，您需要维护一个包含最近 1000 个元素的队列。

要保持运行平均值，请保持最近 1000 个元素的运行总数；当您向队列中添加一个新元素时，您将其值添加到总数中，同时减去您刚刚从队列中删除的最旧元素的值。返回总数除以 1000，然后就可以了。

要保持运行第 N 个百分位数，请维护两个堆并保持堆中元素的计数；“较低”堆具有较低的 N% 值，“较高”堆具有较高的 (1-N)%（例如，较低的第 95 个百分位堆将具有 950 个元素，而较高的第 5 个百分位堆将具有有 50 个元素）。在任何时候，您都可以从上层堆中返回最低的元素，这就是您的百分位数。当您从最近值的队列中删除一个元素时，也从堆中删除该值。如果这使堆不平衡（例如，下部堆有 951 个元素，上部堆有 49 个元素），则移动元素以平衡它们（例如，从下部堆中删除顶部元素并将其添加到上部堆中）。

因为你想要两个百分位，所以使用三个堆 - 下部堆有较低的 950 个元素，中间有接下来的 40 个，上部有最高的 10 个。返回中间堆的最低元素为第 95 个百分位数，最低的元素第 99 个百分位的堆上元素。

添加和删​​除堆元素是 O(lg(n))，因此这是向队列和三个堆添加新元素的成本：从堆中删除最旧的队列元素 (O(lg(n))，添加新的队列元素到适当的堆（O（lg（n）），并在需要时平衡堆（再次，O（lg（n））。将新元素添加到最高元素大于堆的最低堆元素，即

if (newElement < lowestHeap.maxElement) {
    lowestHeap.add(newElement)
} else if (newElement < middleHeap.maxElement) {
    middleHeap.add(newElement)
} else { 
    highestHeap.add(newElement)
}

确保您的堆允许重复元素