ポアソンディスクサンプリングを線形時間で実装する

Question

ノイズ発生器（ポアソンディスクノイズ）を実装しようとしていますが、hereと記載されていますが、hereと記載されていますが、 ランダムアクティブサンプル（この例では赤い点）がアクティブサンプルキューからポップされます。私が知る限り、このステップ自体は線形の複雑さを持っています。これは、サンプルが最後からポップされたりキューの先頭からデキューされず、アルゴリズム全体が2次的になるからです。

ノイズジェネレータを真にリニアにするにはどうすればよいですか？私が知る限り、これは一定の時間内にランダムな要素を取り除くことができるシーケンスを必要とします。

Answer 1

私の知る限り、このキューで実行する必要がある操作は、ランダム要素を選択して削除し、新しい要素を追加することだけです。特に、注文を保存する必要はありません。

これを実装するには、std :: vectorやjava.util.ArrayListなどの可変長配列をサポートするクラスを使用します。要素を追加するには、最後にpush_back（）またはadd（）を追加します。ランダム要素を削除するには、配列内のランダム要素を選択して保存し、保存したばかりの要素の上に要素をコピーしてから、配列のサイズを1減らします。何かのように

インデックス= rng.nex（）tInt（arr.size（））;

toReturn = arr.get（index）;

arr.set（index、arr.get（arr.size（） - 1））;

arr.resize（arr.size（） - 1）;

return to return;