std :: listを無作為化したときのパフォーマンスを改善する

Question

私は現在Fisher-Yatesシャッフルを使ってランダム化しているstd::listを持っています（http://en.wikipedia.org/wiki/Fisher-Yates_shuffle参照）。要約すると、私のコードはリストの次のステップを実行します：

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

リストはランダムアクセスを提供しないため、これは手順1でリスト全体を反復処理していることを意味し、各要素について、反復処理を繰り返しています。 。これは私のプログラムのパフォーマンスの大きなボトルネックなので、私はそれを改善しようとしています。他の理由で私はコンテナとしてlistを使用し続ける必要がありますが、ランダム化機能の開始時にvectorに変換し、最後にlistに変換することを検討しています。私のリストには通常300〜400のアイテムが含まれているので、コンテナ間の変換コストは、アイテムを順番に移動するのを避けるためには価値があると思います。

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

Answer 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()); 

を理解する方がはるかに簡単で、はるかに少ないエラーが発生しやすい、それはですほとんどの場合、おそらくこのコードのほうがあなたのパフォーマンスにとって重要なものでなければなりません（測定で確認したことがあります）。

EDIT：ところで、あなたはWikipediaの記事を見ているので、フィッシャー・イェイツの「裏返し」の変種。