6

我正在创建一个迭代算法（蒙特卡洛方法）。该算法在每次迭代时都会返回一个值，从而创建一个值流。

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

我决定实现它计算最后一个值的max和值，然后使用这个公式计算并将它与:进行比较。如果达到此条件，则停止迭代并返回结果。min1000error(max-min)/minepsilonerror<=epsilon

  1. 第一个愚蠢的想法是对它使用 alist和append新值，在每次附加后计算它的最后一个值的max和值。min1000

  2. 1000然后我决定保留更多的最后一个值是没有用的。于是我想起了deque。deque这是一个非常好的主意，因为在对象两端添加和删除的复杂性是O(1). 但它并没有解决每次迭代都需要遍历所有最后 1000 个值来计算min和的问题max。

  3. 然后我记得有heapq模块。它以这样一种方式保存数据，以便在每一刻都有效地返回最小的一个。但我需要最小的和最大的。此外，我需要保留元素的顺序，以便我可以保留1000算法的最后返回元素，我不知道如何使用heapq.

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

我怎样才能最有效地解决这个任务？

4

6 回答 6

7

如果您自由/愿意更改 的定义error，您可能需要考虑使用variance代替(max-min)/min。

您可以逐步计算方差。诚然，使用这种方法，您不会从流中删除任何值——方差将取决于所有值。但那又怎样？variance/n有了足够的值，前几个对方差的影响不大，当有足够的值围绕某个固定值聚集时，平均值的方差将变小。

因此，您可以选择在variance/n < epsilon.

于 2011-10-24T13:48:05.557 回答
6

作为@unutbu 出色想法的改进，您可以考虑使用指数加权移动方差。它可以在O(1)每次观察时按时间计算，需要O(1)空间，并且具有随着观察变老自动减少观察权重的优点。

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

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

于 2011-10-24T14:08:13.337 回答
4

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 初始化这个数组，然后一个接一个地覆盖它们。nanminand方法忽略了这些nanmaxnan。

于 2011-10-24T13:53:56.357 回答
3

恐怕我现在无法提供一个很好的 Python 答案，但我会给你一个你需要使用的数据结构的大纲：

将您的 1000 个项目保存在 FIFO 队列中。保留指向队列中最大和最小项的指针。如果其中之一离开队列，请在队列中搜索新的最大/最小（摊销成本取决于您的数据）。如果新的最大/最小值进入队列，只需更新指针 (O(1))。假设您的数据正在收敛，这应该可以正常工作。

于 2011-10-24T13:49:11.720 回答
1

创建具有 minvalue 和 maxvalue 属性的 deque 子类。添加或删除条目时，将它们与当前的最小值和最大值进行比较 - 如果要删除的值是当前的最小值或最大值，则只需重新扫描双端队列的最小值/最大值。添加时，只需将新值与当前最小值和最大值进行比较，并进行相应更新。这将优化双端队列的最小/最大值扫描。

于 2011-10-24T13:50:06.880 回答
1

您可以使用两个斐波那契堆。添加值在 O(1) 中，删除在 O(log(n)) 中。在您的问题中，您已经建议了 heapq 模块。我不确定它提供什么样的堆，但一个普通的堆也可以非常顺利地工作。

只能从一个堆中提取最小值而不能提取最大值的问题可以通过保留两个堆来解决。由于我不知道 heapq 模块，你可以提供你自己的比较函数，或者你可以只使用-value而不是value第二个堆的键。

于 2011-10-24T14:18:02.557 回答