C++ iterate vector in modo casuale

Question

Sto lavorando a un programma con multithreading in cui tutti i thread condividono un vettore (di sola lettura). L'obiettivo di ogni thread è di percorrere l'intero vettore. Tuttavia, tutti i thread devono visitare questo vettore in un modo diverso.

Dal momento che il vettore è const e condiviso tra tutti i thread, non posso usare random_shuffle e semplicemente scorrere su di esso. Per ora la mia soluzione è quella di costruire un vettore crossref che conterrà gli indici sopra il vettore condivisa e quindi mischiare questo vettore, cioè

 std::vector<int> crossref(SIZE) ; // SIZE is the size of the shared vector 
    std::iota (std::begin(crossref), std::end(crossref), 0); // Fill with indices ref 
    std::mt19937 g(SEED); // each thread has it own seed. 
    std::shuffle (crossref_.begin(), crossref_.end(), g); // Shuffle it 

Tuttavia, facendo questo rivelano alcuni problemi (1) non è molto efficiente, in quanto ogni thread deve accedere al suo vettore crossref prima di accedere a quello condiviso, (2) ho qualche problema di prestazioni a causa della quantità di memoria richiesta: il vettore condiviso è molto grande e ho un sacco di thread e processori.

Qualcuno ha qualche idea di miglioramento che eviterà la necessità di memoria aggiuntiva?

Answer 1

È possibile utilizzare la nozione algebrica di primitive root modulo n. Fondamentalmente

Se n è un intero positivo, i numeri interi compresi tra 1 e n - 1 che sono coprimi per formare n gruppo di classi primitive modulo n. Questo gruppo è ciclico se e solo se n è uguale a 2, 4, p^k, o 2p^k dove p^k è una potenza di un numero primo dispari

Wikipedia mostra come è possibile generare numeri sotto 7 utilizzando 3 come generatore.

Da questa affermazione si deriva un algoritmo.

1. Prendete il vostro numero di n
2. trovare il prossimo numero primo m che è più grande di n
3. Per ognuno di tuo thread scegliere un numero casuale univoco F(0) tra 2 e m
4. calcolare l'indice successivo utilizzando F(i+1) = (F(i) * F(0)) mod m. Se l'indice è compreso nell'intervallo [0, n], accedere all'elemento. Se non vai verso il prossimo indice.
5. Stop dopo m - 1 iterazioni (o quando si ottiene 1, è la stessa cosa).

Poiché m è primo, ogni numero compreso tra 2 e m-1 è coprimi a m così è un generatore di sequenza {1 ... m}. È garantito che nessun numero verrà ripetuto nei primi passaggi m - 1 e che verranno visualizzati tutti i numeri m - 1.

Complessità:

• Fase 2: fatto una volta, la complessità equivalente a trovare i numeri primi fino ad n, cioè sieve of Eratosthenes
• Fase 3: Fatto una volta, è possibile scegliere 2, 3, 4, 5 , ecc ... Che è basso come O(thread count)
• Passaggio 4: O(m) tempo, O(1) nello spazio per thread. Non è necessario memorizzare la F (i). Hai solo bisogno di sapere il primo valore e l'ultimo valore. Queste sono le stesse proprietà dell'incremento

Answer 2

Se la memoria è il problema più grave, è necessario scambiare i cicli della CPU per lo spazio di memoria.

E.g. std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool) di C++ è un array di bit con una memoria abbastanza efficiente.

Ogni thread può avere il proprio vector<bool> che indica se ha visitato o meno un determinato indice. Quindi dovresti utilizzare i cicli della CPU per scegliere casualmente un indice che non ha ancora visitato e terminare quando tutti gli bool s sono true.

Answer 3

Se ho capito bene che si desidera generare una permutazione casuale in modo incrementale, cioè che si desidera chiamare n volte una funzione f in modo da generare tutti i numeri permutato da 1-n, in modo che la funzione abbia una memoria costante.

Dubito che esista se si desidera ottenere una distribuzione uniforme tra le permutazioni, ma si può essere soddisfatti con un sottoinsieme dell'insieme di permutazioni.

Se questo è il caso si può generare una permutazione prendendo un numero p privilegiata con n e calcolare per ogni i in [1, n]: i.p (mod n). Ad esempio, se si hanno n = 5 e p = 7, quindi 7% 5 = 2, 14% 5 = 4, 21% 5 = 1, 28% 5 = 3, 35% 5 = 0. È possibile combinare diverse funzioni per ottenere qualcosa di soddisfacente per voi ...

Answer 4

Questa non è una risposta completa, ma dovrebbe portarci a una soluzione corretta.

hai scritto alcune cose che potremmo prendere come ipotesi:

(1) non è molto efficiente, in quanto ogni thread ha bisogno di accedere al suo crossref vettore prima di accedere al condiviso una,

È improbabile che sia vero. Stiamo parlando di una ricerca indiretta. A meno che i tuoi dati di riferimento non siano in realtà un vettore di interi, ciò rappresenterà una parte infinitesimale del tuo tempo di esecuzione. Se i dati di riferimento è un vettore di interi, poi basta fare N copie di esso e mescolarle ...

(2) ho qualche problema performance a causa della quantità di memoria richiesta : il vettore è condiviso molto grande e ho un sacco di thread e processori.

Quanto è grande? L'hai misurato? Quanti oggetti discreti ci sono nel vettore? Quanto è grande ciascuno?

Quanti fili?

Quanti processori?

Quanta memoria hai?

Hai profilato il codice? Sei sicuro dove il collo di bottiglia delle prestazioni è? Hai considerato un algoritmo più elegante?

Answer 5

Sembra che il ragazzo this abbia risolto il problema in modo molto carino.

Questo è quello che dice nella prima riga del post: In questo post mostrerò un modo per fare un iteratore che visualizzerà gli elementi in un elenco in un ordine casuale, visiteremo solo ogni elemento una volta e ti dice quando ha visitato tutti gli oggetti ed è finito. Lo fa senza memorizzare una lista mescolata, e inoltre non deve tenere traccia di quali oggetti ha già visitato.

Egli sfrutta la potenza di un algoritmo di cifratura a blocchi a lunghezza di bit variabile per generare ogni singolo indice dell'array.