2

n各要素が選択される確率を示す確率のリストを指定して、リスト内の要素をランダムに描画する最も効率的な方法を探しています。

aList = [3,4,2,1,4,3,5,7,6,4]

MyProba = [0.1,0.1,0.2,0,0.1,0,0.2,0,0.2,0.1]

これは、各描画で、最初の要素 (3) が描画される確率が 0.1 であることを意味します。もちろん、

sum(MyProba) == 1 # 常に True を返す len(aList) == len(MyProba) # 常に True を返す

今まで私は次のことをしました：

def random_pick(some_list, proba):
    x = random.uniform(0, 1)
    cumulative_proba = 0.0
    for item, item_proba in zip(some_list, proba):
        cumulative_proba += item_proba
        if x < cumulative_proba:
            break
    return item

nb_draws = 10
list_of_drawn_elements = []
for one_draw in range(nb_draws):
    list_of_drawn_elements.append(random_pick(aList, MyProba))

動作しますが、長いリストや大きな値の場合は非常に遅くなりますnb_draws。このプロセスの速度を改善するにはどうすればよいですか?

注: 私が直面している特別なケースでは、nb_draws は常に の長さに等しくなりaListます。

4

4 に答える 4

1

一般的な考え方（他の人の回答でも概説されているように）は、サンプルを描画するたびに前処理（累積分布の計算）が行われるため、メソッドが非効率的であるということですが、サンプリングし、前処理されたデータを使用してサンプリングを行います。

前処理とサンプリングは、 Walker のエイリアス メソッドを使用して効率的に行うことができます。少し前に実装しました。ソースコードを見てください。(外部リンクで申し訳ありませんが、ここに投稿するには長すぎると思います)。私のバージョンには NumPy が必要です。NumPy を使用したくない場合は、NumPy を使用しない代替手段もあります (私のバージョンはこれに基づいています)。

編集: Walker のエイリアス メソッドの説明は、最初に提供したリンクにあります。一言で言えば、長方形の「ダーツボード」をどうにかして作成したと想像してください。このダーツボードは、各パーツが元のアイテムの 1 つに対応し、各パーツの面積が、対応するアイテムを選択する望ましい確率に比例するように、パーツに分割されます。エレメント。次に、ダーツボードでランダムにダーツを投げ始め (ダーツが終わった場所の水平方向と垂直方向の座標を指定する 2 つの乱数を生成することによって)、ダーツがヒットした領域を確認できます。エリアに対応するアイテムが選択したアイテムになります。Walker のエイリアス メソッドは、ダーツ ボードを構築する単純な線形時間の前処理です。各要素の描画は、一定時間で実行できます。結局、お絵描きn 個のうちのm 個の要素は、前処理に O( n )のコスト、サンプルの生成にO( m ) のコストがかかるため、総複雑度は O( n + m ) になります。

于 2013-10-29T08:12:08.123 に答える
0

各要素の累積確率範囲を事前に計算し、これらの間隔からツリーを作成してみてください。次に、現在の線形ではなく、生成された確率に対応する要素を検索するための対数複雑度が得られます。

于 2013-10-29T08:18:09.910 に答える