std :: vectorのすべての要素をランダムに1回だけランダムに選択するための効率的な方法

Question

std::vector<T>の各要素へのアクセスをランダムに順番に選択する効率的な方法を探しています。 std::random_shuffleを開き、各要素が1回だけ選択されていることを確認します。

私はTの各インスタンスが非常に大きなオブジェクトである可能性が高く、b）ベクトルの要素で実行する他の操作では、同じ順序にとどまる

さらに、私は実際に重複を拾って拒否する道を歩いて行きたいとは思わない。このランダムな選択メソッドを何度も呼び出すためには、ベクトルに格納されたこれらの大きなオブジェクトがたくさんあり、効率が重要です。

Answer 1

ランダムに全体の配列を繰り返し処理するか、ランダムにいくつかの要素しか必要ないかどうかは教えてください。

最初のケースを想定します。あなたは簿記のための余分なストレージが必要になりますし、とにかくシャッフルのための線形時間が必要になります。それで、順列を作り、あなたが望むようにあなたがそれを再構成できるように、その記憶を生かしてください。

#include <algorithm> 
#include <random> 
#include <numeric> 

struct permutation 
{ 
    permutation(size_t n) 
     : perm(n), g(std::random_device()) 
    { 
     std::iota(perm.begin(), perm.end(), size_t(0)); 
    } 

    void shuffle() { std::shuffle(perm.begin(), perm.end(), g); } 

    size_t operator[](size_t n) const { return perm[n]; } 

private: 
    std::vector<size_t> perm; 
    std::mt19937 g; 
}; 

使用法：C++ 11で

std::vector<huge_t> v; 
... 

permutation sigma(v.size()); 
sigma.shuffle(); 

const huge_t& x = v[sigma[0]]; 

... 
sigma.shuffle(); // No extra allocation 
const huge_t& y = v[sigma[0]]; 

あなたはC++ 03 std::random_shuffleを使用するようにコードを適応させるが、乱数生成器に非常に少数の保証があることに注意してくださいすることができます。

Answer 2

ベクトル内の要素へのポインタを使用する既存のものと同じサイズのベクトルを作成します。代わりにランダムにポインタベクトルをシャッフルして読み込みます。低コストです。

Answer 3

私は最も簡単な（そしてより効率的なものの一つ）ソリューションは、あなたのvectorへのポインタを保持し、あなたのvector<T>、またはstd::vector<T*>にstd::vector<size_t>保持インデックスを作成するために、どちらかだと思います。その後、std::random_shuffleを使ってシャッフルして、それを反復して元のベクトルから対応する要素を選んでください。あなたが元のベクトルとシャッフルポインタの順序を変更しないようにするか、はかなり安いです