快速计算传入号码的最小值、最大值和平均值

这里有一个算法，在某些情况下可以在一定程度上提高效率：

1. 当事件进入时，完全缓冲它们，并计算运行sum、count、min、max（平凡）。

2. 当发出average、min或max的请求时，从缓冲区的后面循环，并开始删除超过一秒的值。从sum中减去，边走边count。

   • 如果值都高于min则可以保留min。如果值低于 max ，则可以保留max。在此方案中，您可以有效地更新average、min和max。

   • 如果值低于 min 或高于 max ，则需要遍历数组的其余部分并重新计算它。

3. 每秒钟左右执行一次第二步，以免缓冲区太满。此代码也可以在每个缓冲区插入上执行，也可以在任何有意义的地方执行。

这种工作的最佳结构是循环缓冲区，以避免内存分配和 GC 妨碍。它应该足够大，以涵盖每秒邮件大小的最坏情况。

更新

根据使用场景，要做的另一件事是运行上述算法，但以 10 x 100ms 块而不是 1 x 1000ms 块运行。也就是说，保持运行最小值、最大值、总和并计数这 10 个块。然后，当您遇到"失效"场景时，您通常只需要查看最新的 100 毫秒数据或快速传递其他 9 个块的最小值和最大值。

---

@ja72提供了一个好主意，可以在最小值和最大值无效时节省查找它们：

x_max保留最小/最大值x_min，而是保留它们在 x[i] 数组中的位置索引，并带有 i_min 和 i_max。然后找到它们有时可能微不足道，但是当考虑的最后一个值包含最小值和最大值时，需要扫描整个列表以建立新的限制。

---

Sam Holder 在评论中还有另一个好主意 - 保留一个始终排序的并行数组，这可以让您从顶部或底部删除数字，以便更轻松地找到新的最小值和最大值。但是，这里的插入速度会受到一点影响（需要保持顺序）。

---

最终，正确的选择将取决于程序的使用特征。读取值的频率与插入频率的比较高？

使用循环缓冲区，每个元素都有时间戳和数据，每秒的最大元素数作为循环缓冲区的大小。

将每个元素插入缓冲区头时，检查缓冲区另一侧的过期时间，删除该元素。

如果删除的元素是最小值或最大值，则必须计算新的最小值/最大值。 如果不是，您将根据新到货更新最小/最大。

对于平均值，保留总数，保留计数，然后除法。

你不能在队列中保留你的数字和他们的到达时间，以及队列中的当前最大值和最小值（可能需要保持值的数量在相同的最小值/最大值）和队列中所有数字的总值和元素计数。

然后，当一个数字到达时，将其添加到队列中并调整最小/最大/值和计数。 然后查看队列的另一端，删除最后一个数字到达后 1 秒内的所有元素，并再次调整最大值/最小值/计数/总值。

然后你不需要在瞬间计算任何东西，只需返回预先计算的东西（即读取最小/最大或总计/计数的当前值）

正如@yaman指出的那样，您不能只保留最小值和最大值，因为当一个被删除时，您可能不知道新的。 在这种情况下，我可能只会保留列表中所有数字的第二份副本，但不是按到达时间排序，而是按值排序。 然后，您只需在此列表中添加和删除每个数字，因此您将始终知道最大值和最小值。 这样您就不必扫描缓冲区中的所有元素才能找到新的最大值/最小值，但代价是保留 2 个副本，但对此列表的更新应该很便宜，因为它已经订购了。

@DanRedux是正确的;每次都需要计算它们，因为您的输入正在发生变化。 现在，您可能更愿意按需或预先（即，当您获得新批次时）计算这些数字，具体取决于需要结果的频率。

例如，如果您的平均用例每 ~30 秒轮询一次这些统计数据，那么我可能会按需计算它们并缓存结果，直到有新的批次出现。 不过，这实际上取决于您的使用场景。

至于如何存储它们，你真的别无选择，是吗？ 您需要为内存中的所有 50,000 个数字留出空间。 所以。。。您需要足够大的内存块来容纳它们。 为了避免每次出现新序列时不断分配 2KB，您最好声明一个足够大的数组来容纳尽可能大的数据集并重用它。 同样，这归结为您的需求，即，您知道最大可能的数据集是多少吗？ 随着时间的推移，分配新的内存块是否会导致应用程序出现问题？

如果最后N值的平均值x[0].. x[N-1]是m_1（x[0]是最新值，x[N-1]是考虑的最后一个值），则值的平均m_2将所有内容推回一个索引并将值x为

 m_2 = m_1+(x-x[N-1])/N;
 for(i=N-1;i>0;i--) { x[i]=x[i-1]; }
 x[0] = x;

与其保持最小/最大值x_min，x_max保留它们在x[i]数组中的位置的索引，并带有 i_min 和 i_max 。然后找到它们有时可能微不足道，但是当考虑的最后一个值包含最小值和最大值时，需要扫描整个列表以建立新的限制。

有一种有效的方法来跟踪给定时间窗口内的最小（或最大）值，而通常不必存储该窗口内到达的所有数字。 （但是，最坏的情况仍然需要存储所有数字，因此您需要为所有数字保留空间，或者接受有时可能会得到不正确的结果。

诀窍是只存储以下值：

1. 已在时间窗口内到达，并且
2. 小于（或大于）任何以后的值。

实现这一点的合适数据结构是存储值及其到达时间的简单循环缓冲区。 您需要在缓冲区中维护两个索引。 以下是该算法的简单英文描述：

启动时：

• 分配一个val值的 N 元素缓冲区和一个time时间戳的相应 N 元素缓冲区。
设 imax = 0（或介于 0 和 N−1
• 之间的任何其他值（包括 0 和 N−1），设 inext = imax 。 这表示缓冲区当前为空。

当在时间t收到新值new时：

• 当 imax ≠ inext 和 time[imax] 超出区间时，递增 imax 1（模 N）。
• 当imax ≠ inext和val[inext-1] ≥ new时，递减inext 1（模N）。
• 设 val[inext] = new 和 time[inext] = t 。
• 如果inext ≠ imax-1，则inext递增 1（模 N）;否则适当地处理"缓冲区已满"条件（例如，分配更大的缓冲区，抛出异常，或者只是忽略它并接受最后一个值没有正确记录）。

请求最小值时：

• 当 imax ≠ inext 和 time[imax] 超出区间时，将imax递增 1（模 N）。
• 如果imax ≠ inext，则返回val[imax];否则返回一个错误，指示在时间间隔内未收到任何值。

如果接收的值是独立且分布相同的（并且作为泊松过程到达），我相信可以证明在任何给定时间存储在列表中的平均值数为 ln（n+1），其中 n 是在时间间隔内接收到的值的平均数。 当 n = 50,000 时，ln（n+1） 和大约 10.82。 但是，应该记住，这只是平均值，偶尔可能需要数倍的空间。

---

对于平均水平来说，不幸的是，同样的技巧不起作用。 如果可能的话，您可以切换到指数移动平均线，可以使用非常小的空间轻松跟踪（平均值只有一个数字和一个指示上次更新时间的时间戳）。

如果这是不可能的，但你愿意接受平均值中的少量平滑，你可以计算一个平均值，比如每毫秒。 这样，每当请求最后一秒的值的平均值时，您都可以取过去 1001 毫秒平均值的平均值，根据间隔内毫秒的数量来加权其中最旧和最新的：

启动时：

设
• 间隔为要平均的时间间隔的长度，设 n 为子区间数。
• 设 dt = 区间/n。
• 分配一个sum值的 n+1 元素缓冲区和cnt非负整数的 n+1 元素缓冲区，并用零填充两者。
• 让prev有任何价值。 （这并不重要。

当在时间t收到新值new时：

• 设 i = floor（ t/dt） mod （n+1）。
• 如果i ≠ prev：
  • 从total中减去sum[i]，从count中减去cnt[i]。
  • 设 sum[i] = 0，cnt[i] = 0，设 prev = i 。
• 将new添加到sum[i]并将cnt[i]递增 1。
• 将new添加到total并将count递增 1。

当在时间t请求平均值时 ：

• 设 i = floor（ t/dt） mod （n+1）。
• 如果i ≠ prev：
  • 从total中减去sum[i]，从count中减去cnt[i]。
  • 设 sum[i] = 0，cnt[i] = 0，设 prev = i 。
设 j = （ i −n） mod （n+1）
• = （ i +1） mod （n+1）。
设 w = frac（ t/dt） = （ t/dt
• ） − floor（ t/dt）。
• 返回 （ total − w × sum[j] ）/（ count − w × cnt[j] ）。

可悲的是，没有。这是不可能的原因是因为你只需要考虑一秒钟前的它们，这意味着你每次都必须重新计算结果，这意味着巨大的循环。

如果你想计算最后的40,000个数字，或者所有数字，它会更容易，但由于它是基于时间的，所以你必须每次都遍历整个列表。

有没有办法在不使用数组或列表（缓冲区）的情况下做到这一点 存储到达数字并计算结果？

不。 正如您所说，如果不存储信息，就不可能做到这一点。 不过，您可以稍微调整一下要求以摆脱对缓冲区的需求。

如果我需要使用缓冲区，实现的有效方法是什么 这？

为此，您需要使用队列。

添加项目时，如果是新的最大值或最小值，请相应地调整这些变量。 您可以通过此处的公式逐步调整平均值。 只需将新值减去平均值，除以集合中的新项目数（即队列大小加一），然后将其添加到旧平均值中。

然后你会或多或少地得到这样的东西：

while(queue.Peek < oneSecondAgo)
{
  oldItem = queue.Peek
  queue.Dequeue();
  if(oldItem == min) //recalculate min
  if(oldItem == max) //recalculate max
  mean += SubtractValueFromMean(oldItem.Value, queue.Count);
}

要从平均值中删除值，您应该能够使用相同的公式进行加法，但使用值的负数而不是正数...我认为。 一个更好的数学家可能需要在这里帮助你。

如果数字一个接一个地出现，则使用秒表和 while 循环在一秒钟内逐个获取每个数字，并计算最小值、最大值和平均值。

double min = double.MaxValue;
double max = double.MinValue;
double sum = 0;
int count = 0;
double avg;
StopWatch sw = new StopWatch();
sw.Start();
while(sw.Elapsed.TotalSeconds <= 1)
{
   // Get the next number in the stream of numbers
   double d = GetNextNumber();
   // Calculate min
   if(d < min) min = d;
   // Calculate max
   if(d > max) max = d;
   // Calculate avg = sum/ count
   sum += d;
   count++;
}
avg = sum/count;

然后返回最小值、最大值和平均值。

如果不保留缓冲区或队列中的数字，就不可能做到这一点。

原因很简单：当最大值到期（超出 1 秒窗口）时，新的最大值是在最后一秒内到达的其他数字，因此您需要记录可能成为新最大值的候选值。

需要平均值意味着所有值在过期时都会产生影响，并且在一秒钟之前不会丢弃任何东西。

Sam Holder 关于使用队列的建议很好，尽管您可能需要一个专门的队列，可以同时将列表按两个顺序保存：接收号码的顺序（到达时间），以及从最大到最小排序。

使用具有两个下一个指针和两个前一个指针（一个暂时配对，另一个在大小方面）的单个节点对象

可以同时从两个列表中删除元素，当元素从临时列表中过期时，您可以访问大小列表的指针，因为它们位于同一个节点对象中。

可以通过保持运行总计和运行计数，在删除元素时减去元素并在创建元素时添加元素来维护平均值，因此不必每次都迭代整个列表来计算平均值。

正如 btilly 在他们对 Sam holder 帖子的评论中所建议的那样，使用最大堆和最小堆比使用列表更有效，我们再次需要使用带有指针的单个节点堆和列表，所以我们不必搜索元素来删除它们， 并且可能需要花一些时间考虑如何正确删除不在堆顶部的元素，同时保持 O（log n） 插入和删除的保证。

平均而言，需要考虑 3 种情况：

1. 您的数字是整数。 保持运行总计和计数，添加新的值到总计，从总计中减去旧值，然后除以根据需要计数。 这很简单，因为您不必担心精度下降。
2. 您的数字是浮点数，您需要 0 损失精度：您必须遍历整个一秒列表以计算平均值
3. 你的数字是浮点数，你可以忍受一些损失精度：像整数平均值一样操作，做一个完整的每 1000 个值左右重新计算一次。

对于最小值和最大值（仅与上面的 #1 和 #3 相关）：

• 将值保留在按值编制索引的 treap 中。
• 还要将值保存在按时间排序的双向链表中。 保存开头和结尾列表。
• 从列表的开头删除，并添加到列表。
• 对于每个新值：将其添加到时间链表的开头。根据需要从时间链表的末尾删除值。

在链表中添加和删除值时，对 treap 执行相应的操作。要从 treap 中获得最小值和最大值，只需在 log（n） 时间内执行 find_minimum 和find_maximum操作。 当您在常量时间内从链表的右端删除内容时，也要在 log（n） 时间内将它们从 treap 中删除。

Treaps 可以在 log（n） 时间内找到它们的最小值，在 log（n） 时间内找到

它们的最大值，并在 log（n） 时间内找到任意值。 通常，访问数据所需的不同方式越多，像 treap 这样的全面数据结构看起来就越好。