2016-06-28 25 views
7

Ho due vettori con lo stesso numero di elementi, ma i loro tipi hanno dimensioni completamente diverse. Ho bisogno di mescolarli in modo che entrambi abbiano lo stesso ordine dopo aver mischiato (ogni elemento in un vettore è correlato a ciascun elemento nell'altro). Il modo che ho trovato per farlo era:`std :: shuffle` garantisce lo stesso ordine con le stesse sementi su vettori diversi?

// sizeof(a[0]) != sizeof(b[0]) 
// a.size() == b.size() 
{ 
    std::mt19937 g(same_seed); 
    std::shuffle(a.begin(), a.end(), g); 
} 
{ 
    std::mt19937 g(same_seed); 
    std::shuffle(b.begin(), b.end(), g); 
} 

Posso stare certi che entrambi i vettori saranno mescolate allo stesso modo? Questa implementazione dipende? Ho una tale garanzia dalla specifica std::shuffle?

+4

Probabilmente sarebbe meglio comprimerli in un vettore di coppie prima di eseguire la riproduzione casuale, oppure creare un nuovo vettore di indici, mescolarlo e utilizzarlo per indicizzare nei vettori paralleli. – Taywee

+0

Il mio primo tentativo è stato il vettore degli indici, ma i miei dati sono grandi e non si adattano a due copie nella mia memoria, quindi ho provato a caricarlo dal disco nell'ordine mescolato, che ovviamente era follemente lento. Così ho fatto in questo altro modo per essere in grado di leggere dal disco in sequenza (molto veloce) e shuffle sul posto (nessuna doppia memoria). – lvella

+0

Le specifiche non garantiscono questo, anche se è difficile immaginare un'implementazione che non darebbe i vincoli che lo standard mette su shuffle. L'algoritmo 'suffle' stesso sembra abbastanza semplice da scrivere, quindi scriverò la mia implementazione che mi darebbe la garanzia. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle – Galik

risposta

8

C'è una dichiarazione interessante riordino nella specifica:

Osservazioni: Nella misura in cui l'attuazione di questa funzione fa uso di numeri casuali, l'oggetto g funge da fonte implementazione di casualità.

Anche così, questa affermazione non ti aiuta. La sezione "Osservazioni" è testo normativo, quindi questo sta dicendo che g fornirà i numeri casuali per determinare l'ordine mescolato. Tuttavia, non dichiara che g è l'unico fattore che determina la permutazione.

Mentre la dimensione del valore del contenitore probabilmente non ha importanza, non c'è la garanzia che alcune proprietà del tipo non influenzino qualcosa. Ad esempio, se il tipo di valore fosse banalmente riproducibile, un'implementazione potrebbe utilizzare una versione diversa della funzione che utilizzava un algoritmo leggermente diverso. Tuttavia, se fosse un valore di dimensioni di registro, potrebbe non farlo.

In breve, no, std::shuffle non garantisce quello che stai cercando.