获取数据流的平均值、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）个元素的最小堆（heapA）
2. 一个 maxheap 用于存储剩余 990 个（或 950 个元素）（heapB）
3. 保持元素顺序的最小堆。最旧的元素始终位于该堆的顶部 heapC)

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

这就是它的工作原理：

1. 假设系统中有 1000 个元素。 heapA 有 10 个元素，heapB 有 990 个元素，heapC 有 1000 个元素
2. 从系统中删除最旧的元素。从 heapC 中删除它并使用链接从 heapA 或 heapB 中删除它
3. 重新平衡三个堆。
4. 根据 heapA 顶部将新元素的顺序添加到 heapA 或 heapB 中
5. 将元素的顺序添加到heapC。
6. 执行此操作时，还要添加彼此的链接。

Answer 3

我们可以使用 std::multiset 而不是堆来做到这一点。有 2 个多重集并执行与堆相同的算法。