c++ - 2次元グリッドからの異なるランダムポイント

Question

大きな2次元グリッド、たとえば10000 X 10000があります。これらのグリッドから、1000個のランダムなポイントを選択する必要がありますが、2つのポイントが同じにならないように注意する必要もあります。私の頭に浮かぶ標準的な方法は、すべてのポイントを選択した後、そのポイントがすでに選択されているかどうかを確認するために以前のすべてのエントリをチェックする必要がありますが、大きなグリッドと多数のポイントの場合、これは非効率になるようです。それを行うためのより良い方法はありますか？私はC++を使用しています

Answer 1

大きなグリッドと多数のポイントの場合、これは非効率的になります

必ずしも。非効率の潜在的な原因は2つあります。

1. 棄却サンプリングによって引き起こされるオーバーヘッド（つまり、まだ選択されていないポイントが見つかるまで試行を続ける必要があります）。ポイントの0.001％を選択しているとすると、同じポイントを2回ランダムに選択する可能性は非常に低くなります。したがって、再試行のコストはごくわずかです。
2. ランダムに選択されたポイントがすでに選択されているかどうかのチェックのオーバーヘッド。以前に選択したすべてのポイントを適切なデータ構造に保存すると、これをO(1)時間内に実行できます。このためにstd::unordered_setは、良い候補になります。セットのサイズは、選択する必要のある要素の数に比例して大きくなり、グリッドサイズに完全に依存しなくなります。

Answer 2

次のようなアルゴリズムを実装できます。

1. ハッシュからポイントへの空のマッピングを作成します
2. ランダムな点を選択
3. ハッシュを計算する
4. マッピングでハッシュする場合は、1に進みます
5. ハッシュとポイントを保存
6. まだ十分なポイントがない場合は、1に進みます

Answer 3

ランダムに任意のポイントを選択し、それが[選択されたポイント]リストに存在する場合はそれを破棄することは、選択されたポイントのコレクションが適切にソートされていて、簡単に挿入できる限り、非効率的ではありません。

また、ポイントがどのように定義されているか（つまり、それぞれが定義したクラスまたは構造体に関連付けられているか）に応じて、という名前のブール変数をポイントオブジェクトに追加できますSelected。ポイントを選択したら、それがとしてマークされているかどうかを確認しますSelected。そうでない場合は、それをリストに追加し、Selected値をに変更しますTRUE。それ以外の場合は、ランダムポイントの選択を続行します。