Metodo efficiente per selezionare in modo casuale tutti gli elementi di un vettore std :: esattamente una volta senza rimpasto

Question

Sto cercando un metodo efficiente per selezionare l'accesso a ciascun elemento di un std::vector<T> in un ordine casuale, senza rimescolare o copiarli cioè nessun uso di std::random_shuffle e assicurati che ogni elemento sia selezionato una sola volta.

Non voglio copiare o rimescolare come a) ogni istanza di T è probabile che sia un oggetto molto grande eb) per altre operazioni che farò sugli elementi del vettore, è più facile per loro rimanere nello stesso ordine.

Inoltre, in realtà non voglio andare per strada a raccogliere e rifiutare continuamente duplicati. Probabilmente avrò molti di questi oggetti di grandi dimensioni memorizzati nel vettore e l'efficienza è fondamentale, poiché cercherò di chiamare questo metodo di selezione casuale molte volte al secondo.

Answer 1

Non ci hai detto se vuoi ripetere l'intero array casualmente, o se hai solo bisogno di alcuni elementi a caso .

Presumo il primo caso. Avrai bisogno di spazio aggiuntivo per la contabilità e avrai comunque bisogno di un tempo lineare per la mischia. Crea quindi una permutazione e mantieni viva la memoria in modo da poterla rimescolare come desideri. Con C++ 11:

#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; 
}; 

Usage:

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

È possibile adattare il codice per utilizzare C++ 03 std::random_shuffle, ma vi prego di notare che ci sono pochissime garanzie sul generatore di numeri casuali.

Answer 2

Creare un vettore della stessa dimensione di quello esistente che utilizza i puntatori agli elementi nel vettore. Mescola casualmente il vettore puntatore e leggi da lì - è a basso costo.

Answer 3

Penso che la soluzione più semplice (e uno di quelli più efficienti) sarebbe quello di creare un std::vector<size_t> indici che tengono nella vostra vector<T>, o un std::vector<T*> tenendo i puntatori nella vostra vector. Quindi puoi rimescolare quello usando std::random_shuffle, scorrere su di esso e scegliere gli elementi corrispondenti dal tuo vettore originale. In questo modo non cambi l'ordine del tuo vettore originale e puntatori shuffleing o size_t è piuttosto economico