boost :: randomを使用して、要素が削除されているstd :: listから選択する

Question

これを参照してください 関連する質問 ブーストランダムライブラリのより一般的な使用について。

私の質問には、anからランダムな要素を選択することが含まれます std::list, 、いくつかの操作を行います。これには、リストから要素の削除を強力に含めることができ、ある程度の条件が満たされるまで別のランダム要素を選択できます。

ブーストコードとループの場合は、次のように見えます。

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

私の問題は、要素で実行される操作が要素を削除するとすぐに、variate_generatorがリスト内の無効なインデックスを選択する可能性があることです。特に時間とともにシードする場合、毎回variate_generatorを完全に再現することは理にかなっているとは思いません。

Answer 1

私はそれを想定しています MyClass & mc = myList.begin() + index; beginがイテレーターを返しているので、単なる擬似コードです。 operator+.

私が知る限り、この場合の3つの基本的なオプションは次のとおりです。

• アイテムを削除するときに発電機を再作成します。
• 生成されたインデックスをフィルタリングし、> =リストの現在のサイズの場合は、有効なインデックスが取得されるまで再試行します。多くのインデックスを削除すると、これもかなり非効率的になる可能性があることに注意してください。
• リストにノードを残しますが、そのインデックスで操作しようとする場合は無効にマークします。これは、2番目のオプションの別のバージョンです。

あるいは、コンテナの変化するサイズに適応できる別のインデックス生成アルゴリズムを考案することができます。

Answer 2

コンストラクター内のコンテナを受け入れ、均一_Intを集約し、コンテナがサイズを変更するたびに均一なdistributionを再作成する独自の均一な_conted_int配布クラスを作成することができます。を見てください Uniform_intの説明 配布を作成するために実装する必要がある方法。

Answer 3

パフォーマンス面ではもっと心配する必要があると思います。特にこれ：

std::list<MyClass> myList;
myList.begin() + index;

特に速い方法ではありません index-th要素。

私はそれを次のようなものに変換します（これはリストのランダムなサブセンスで動作するはずです）：

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

要素のランダムな順列が必要ない場合。