获取数据流的平均值、P95和P99

Question

获取数据流的平均值、P95和P99

13

我有一些输入数据，想要计算这些数据的平均值、95th和99th百分位数，我最感兴趣的是最后1000个值。任何时候，我都希望查询此对象以获取任何三个值之一（可以在任何时候发生，而不仅仅是当看到数字mod 1000为0时）。有没有办法在不保留最后1000个样本的情况下获得这三个值？

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

（我将在C++中完成此操作，但我认为这并不重要）

- jamesatha

我认为你可以轻松地保存1000个条目的数组，而不会有太多麻烦或内存惩罚。问题在于数据的排序（如果你想要得到百分位数，我认为你需要对其进行排序）。 - Barranka

是的，排序是可能会引起最多麻烦的部分。 - jamesatha

1

我认为如果你没有将数据存储在数组中，就无法计算任何百分位数，因此算法（我认为应该是）如下：1. 存储数据；2. 使用您喜欢的方法对数据进行排序；3. 获取所需位置的值（array[n]，其中 n = round(array.length * p)，且 0<=p<=1）。 - Barranka

2个回答

1

首先，假设您有能力存储1000个数字（假设k次1000，其中k是一个常数）。

保留3个堆：

一个最小堆来存储10（或50）个元素（heapA）
一个最大堆来存储剩余的990（或950个元素）（heapB）
一个最小堆来保持元素的顺序。最旧的元素始终位于此堆heapC的顶部

这三个堆是特殊的：heapC还保持与heapA或heapB中相应元素的链接。heapA和heapB也跟踪heapC中的相同元素。

它的工作方式如下：

假设系统中有1000个元素。heapA有10个元素，heapB有990个元素，heapC有1000个元素
从系统中删除最旧的元素。从heapC中删除它，并使用链接从heapA或heapB中删除它
重新平衡三个堆。
将新元素的顺序添加到heapA或heapB中，具体取决于heapA的顶部
将元素的顺序添加到heapC中。
在执行此操作的同时，还要添加彼此之间的链接。

- ElKamina

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zim-Zam O'Pootertoot · Accepted Answer

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

为了计算平均值，需要维护一个包含最近1000个元素的总和；当添加新元素到队列时，将其值加到总和中，并减去刚从队列中移除的最老元素的值。将总和除以1000即可得到平均值。

为了计算第N个百分位数，需要维护两个堆并计算堆中元素的数量；“较低”的堆包含较低的N%的值，“较高”的堆包含较高的(1-N)%的值（例如，较低的95th百分位数堆将有950个元素，较高的5th百分位数堆将有50个元素）。在任何时候，可以从较高的堆返回最小元素，这就是所需的百分位数。当从最近值的队列中移除元素时，也要从堆中移除该值。如果这使堆不平衡（例如，较低的堆有951个元素，较高的堆有49个元素），则移动元素以平衡它们（例如，从较低的堆中删除顶部元素并将其添加到较高的堆中）。

由于需要计算两个百分位数，因此需要使用三个堆-较低的堆包含较低的950个元素，中间的堆包含接下来的40个元素，较高的堆包含最高的10个元素。返回中间堆的最小元素作为95th百分位数，返回较高堆的最小元素作为99th百分位数。

添加和删除堆元素的时间复杂度为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)
}

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