动态列表最后1000个值的最小值和最大值

Question

我正在创建一个迭代算法（蒙特卡洛方法）。这个算法在每次迭代时都会返回一个值，形成一串值。

我需要分析这些值，并在比如说有 1000 个返回值在某个 epsilon 范围内时停止算法。

我决定通过计算最近 1000 个值的 max 和 min 来实现，然后用这个公式 (max-min)/min 计算 error，并将其与 epsilon 进行比较：error<=epsilon。如果满足这个条件，就停止迭代并返回结果。

1. 我最初的想法是使用一个 list，每次添加新值时都将其附加到列表中，并在每次添加后计算最近 1000 个值的 max 和 min。

2. 然后我意识到没有必要保留超过 1000 个最近的值。所以我想到了 deque。这是个很好的主意，因为在 deque 对象的两端添加和删除的复杂度是 O(1)。但这并没有解决每次迭代都需要遍历最近 1000 个值来计算 min 和 max 的问题。

3. 接着我想到了 heapq 模块。它以一种高效的方式存储数据，可以随时返回最小值。但我需要同时获取最小值和最大值。此外，我还需要保持元素的顺序，以便能够保留算法最近返回的 1000 个元素，而我不知道如何用 heapq 来实现这一点。

考虑到这些想法，我决定在这里询问：

我该如何以最有效的方式解决这个任务？

Answer 1

那numpy怎么样呢？

我们来比较一下速度：

import numpy as np
a = range(1000)
b = np.arange(1000)

max(a) # 29.7us
b.max() # 7.29us

而且你可以无限次地写入这个数组：

i = 0
b = np.empty([1000]) + np.nan

your loop:
    b[i % 1000] = value
    i += 1

超过1000次的值会被覆盖掉。你可以用 np.nanmin(b) 和 np.nanmax(b) 来获取最小值和最大值。

这里的 nan 是指你一开始把这个数组初始化为1000个nan，然后一个一个地把它们覆盖掉。nanmin 和 nanmax 这两个方法会忽略这些nan值。

Answer 2

作为对@unutbu这个好主意的进一步完善，你可以考虑使用指数加权移动方差。这种方法每次观察时只需要O(1)的时间来计算，占用O(1)的空间，并且随着观察时间的增加，它会自动降低旧数据的权重，这样可以更好地反映最新的数据。

相关的公式可以在以下论文中找到：链接。你可以查看其中的公式（140）到（143）。

最后，你可能想用标准差而不是方差。标准差就是方差的平方根，它的单位和原始数据是一样的，这样可以更容易地制定出有意义的停止标准。

Answer 3

如果你愿意改变一下对error的定义，可以考虑用variance（方差）来代替(max-min)/min这个计算方法。

你可以逐步计算方差。确实，使用这种方法时，你不会从数据流中删除任何值——方差会依赖于所有的值。但这有什么关系呢？只要数据量足够大，最开始的几个值对方差的影响就不大了。而且，当很多值聚集在某个固定值附近时，平均值的方差variance/n会变得很小。

所以，你可以选择在variance/n < epsilon时停止计算。