11

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

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

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

4

2 回答 2

7

至少，您需要维护一个包含最近 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)
}

确保您的堆允许重复元素

于 2013-05-08T23:19:37.853 回答
1

首先让我们假设您有能力存储 1000 个数字（假设 k 乘以 1000，其中 k 是常数）。

保留 3 堆：

  1. 用于存储 10（或 50）个元素（heapA）的 minheap
  2. 用于存储剩余 990（或 950 个元素）的 maxheap (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. 将元素的顺序添加到堆C。
  6. 在执行此操作时，还要添加彼此的链接。
于 2013-05-08T23:20:38.543 回答