6

反復アルゴリズム (モンテカルロ法) を作成しています。アルゴリズムは反復ごとに値を返し、値のストリームを作成します。

これらの値を分析し、1000返された値がepsilon.

最後の値のmaxとの値の計算を実装してから、この式を使用して を計算し、:と比較することにしました。そして、この条件に達したら、反復を停止して結果を返します。min1000error(max-min)/minepsilonerror<=epsilon

  1. 最初の頭脳明晰なアイデアは、それに新しい値を使用し、list追加appendするたびに最後の値のmaxand値を計算することでした。min1000

  2. 1000次に、最後の値をこれ以上保持しても意味がないと判断しました。を思い出しましたdeque。dequeオブジェクトの両端での追加と削除の複雑さはO(1). minしかし、各反復で最後の 1000 個の値をすべて調べてとを計算する必要があるという問題は解決しませんでした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)スペースが必要であり、観測が古くなるにつれて観測の重みを自動的に減らすという利点があります。

次の論文には、関連する式があります:リンク。その中の式（１４０）～（１４３）を参照されたい。

最後に、分散ではなく標準偏差を使用したい場合があります。これは単に分散の平方根であり、元のデータと同じ単位を持つという利点があります。これにより、意味のある停止基準を策定しやすくなります。

于 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メソッドはnanmaxこれらのnanを無視します。

于 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 に答える