4

Boost Random ライブラリのより一般的な使用方法については、この関連する質問を参照してください。

私の質問には、 からランダムな要素を選択し、std::list何らかの操作を実行することが含まれます。これには、リストから要素を削除し、別のランダムな要素を選択することが含まれる可能性があります。条件が満たされるまで。

ブースト コードと for ループは、おおよそ次のようになります。

// 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 がリスト内の無効なインデックスを選択する可能性があることです。特に time(0) でシードする場合、variate_generator を毎回完全に再作成するのは意味がないと思います。

4

3 に答える 3

2

MyClass & mc = myList.begin() + index;begin がイテレータを返し、リスト イテレータ (非ランダム アクセス) がサポートされているとは思わないため、これは単なる疑似コードであると想定していますoperator+。

私が知る限り、変量ジェネレーターを使用すると、この場合の 3 つの基本的なオプションは次のようになります。

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

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

于 2010-05-20T13:54:58.520 に答える
1

コンストラクターでコンテナーを受け入れ、uniform_int を集約し、コンテナーのサイズが変わるたびに uniform_distribution を再作成する、独自の uniform_contained_int 分散クラスを作成できます。ディストリビューションを作成するために実装する必要があるメソッドの uniform_intの説明を見てください。

于 2010-05-20T13:56:42.557 に答える
0

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

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

index-番目の要素を取得するための特に高速な方法ではありません。

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

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--

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

于 2010-05-20T13:59:49.833 に答える