1

std::list現在、Fisher-Yates shuffle を使用してランダム化しています ( http://en.wikipedia.org/wiki/Fisher-Yates_shuffleを参照)。要約すると、私のコードはリストの次の手順を実行します。

  1. の各要素をループしますlist。
  2. 要素を、それ自体を含め、現在の位置からランダムに選択された要素と交換します。

リストはランダム アクセスを提供しないため、これは、ステップ 1 でリスト全体を反復処理していることを意味し、要素ごとに、平均してその時点以降の残りの要素の半分を反復処理しています。これは、私のプログラムのパフォーマンスにおける大きなボトルネックであるため、改善を検討しています。list他の理由で、コンテナーとして引き続き使用する必要がありますvectorが、ランダム化関数の開始時に に変換listし、最後に に戻すことを検討しています。私のリストには通常 300 ～ 400 個のアイテムが含まれているため、アイテムを順番にトラバースすることを避けるために、コンテナー間の変換コストに見合うだけの価値があると思います。

私の質問は、これがコードを最適化する最良の方法のように思えますか? より良い方法はありますか？

4

1 に答える 1

4

簡単な改善の 1 つは、データをベクトルにコピーし、ベクトルをシャッフルして、リストにコピーし直すことです。これは、Max と PeskyGnat のコメントで提案されたものです。

vector<int> myVector(myList.size());
copy(myList.begin(), myList.end(), myVector.begin());
random_shuffle(myVector.begin(), myVector.end());
list<int> myListShuffled(myVector.begin(), myVector.end());

この実装はかなり高速です。ただし、ベクトルに対して 3 つのパスを実行するため、シャッフルを自分で実装することで 2 つのパスに減らすことができます。

vector<int> myVector(myList.size());
int lastPos = 0;
for(list<int>::iterator it = myList.begin(); it != myList.end(); it++, lastPos++) {
    int insertPos = rand() % (lastPos + 1);
    if (insertPos < lastPos) {
        myVector[lastPos] = myVector[insertPos]; 
    }

    myVector[insertPos] = *it;
}

list<int> myListShuffled(myVector.begin(), myVector.end());

最初のバージョンの方がはるかに理解しやすく、エラーが発生しにくいため、ほとんどの場合、最初のバージョンの方が望ましいです...おそらく、このコードのビットがパフォーマンスにとって重要である場合を除きます (そして、測定でそれを確認しました)。

編集: ところで、Wikipedia の記事を見ているので、2 番目のコード サンプルでは、​​Fisher-Yates の「インサイド アウト」バリアントを使用しています。

于 2012-04-17T19:31:45.323 に答える