获取数据流的平均值、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)
}

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

Answer 2

首先，让我们假设您可以存储1000个数字(假设k乘以1000，其中k是一个常量)。

保留3堆：

1. 用于存储10个(或50个)元素的minheap (HeapA)
2. 用于存储剩余990个(或950个元素)(HeapB)的maxheap (HeapB)
3. 用于保持元素顺序的minheap。最旧的元素总是在这个堆的顶部)

这三个堆是特殊的: heapC还保留了到heapA或heapB中相应元素的链接。heapA和heapB还跟踪heapC中的相同元素。

这是它的工作方式：

1. 假设系统中有1000个元素。heapA有10个元素，heapB 990和heapC有1000个元素，是系统中最旧的元素。将其从heapC中删除，然后使用链接将其从heapA中删除或将其从三个堆中删除。
2. 将新元素的顺序添加到heapA或heapB中，具体取决于heapA
3. 将元素的顺序添加到heapC中。
4. 执行此操作时，还会添加彼此的链接。