更改列表的最后1000个值的最小值和最大值

Question

我正在创建一个迭代算法(蒙特卡罗方法).该算法在每次迭代时返回一个值,从而创建一个值流.

我需要分析这些值并在说1000返回的值有些时停止算法epsilon.

我决定实现其计算max和min最后的值1000值,然后计算出error使用这个公式(max-min)/min,并把它比作epsilon:error<=epsilon.如果达到此条件,请停止迭代并返回结果.

第一个hare-brained想法是使用a list和appendnew值,计算每次追加后的最后一个值的值max和min值1000.
然后我决定不再保留更多的1000最后价值.所以我记得deque.这是一个非常好的主意,因为在deque对象的两端添加和删除的复杂性是O(1).但是它并没有解决需要在每次迭代中计算min和计算所有最后1000个值的问题max.
然后我记得那里有heapq模块.它使数据保持在每时每刻高效返回最小数据的方式.但我需要最小和最大的.此外,我需要保留元素的顺序,以便我可以保留1000算法的最后返回元素,我不知道如何实现它heapq.

考虑到所有这些想法,我决定在这里问:

如何最有效地解决此任务？

Answer 1

如果您有空/愿意更改您的定义error,您可能需要考虑使用variance而不是(max-min)/min.

您可以逐步计算方差.是的,使用此方法,您不会从流中删除任何值 - 方差将取决于所有值.但那又怎么样？有了足够的值,前几个对方差无关紧要variance/n,当有足够的值聚集在某个固定值附近时,平均值的方差会变小.

所以,你可以选择停止时variance/n < epsilon.

Answer 2

作为@ unutbu优秀创意的改进,您可以考虑使用指数加权移动方差.它可以按照O(1)每次观察的时间计算,需要O(1)空间,并且具有随着观察变老而自动降低观察重量的优点.

以下论文有相关公式:链接.参见其中的等式(140) - (143).

最后,您可能希望使用标准偏差而不是方差.它只是方差的平方根,并且具有与原始数据具有相同单位的优点.这应该可以更容易地制定有意义的停止标准.