algorithm - 获取数据流的平均值，p95和p99

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

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

(我将使用C++进行此操作，但我认为这并不那么重要)

最佳答案

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

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

为了保持第N个百分位数运行，请维护两个堆，并对堆中的元素进行计数。 “较低”的堆具有较低的N％值，而“较高”的堆具有较高(1-N)％的值(例如，较低的95％堆将具有950个元素，而较高的5％堆将具有950个元素)有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)
}

确保您的堆允许重复的元素

关于algorithm - 获取数据流的平均值，p95和p99，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16451236/