Selezionare elemento casuale in un unordered_map

Question

definisco un unordered_map come questo:

std::unordered_map<std::string, Edge> edges; 

C'è un modo efficace per scegliere un bordo a caso dai bordi unordered_map?

Answer 1

Questo è come è possibile ottenere elemento casuale da una mappa:

std::unordered_map<std::string, Edge> edges; 
iterator item = edges.begin(); 
int random_index = rand() % edges.size(); 
std::advance(item, random_index); 

Oppure dare un'occhiata a this answer, che fornisce la seguente soluzione:

std::unordered_map<std::string, Edge> edges; 
iterator item = edges.begin(); 
std::advance(item, random_0_to_n(edges.size())); 

Answer 2

Pre-C++ soluzione 11 :

std::tr1::unordered_map<std::string, Edge> edges; 
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin(); 
std::advance(random_it, rand_between(0, edges.size())); 

C++ 11 in poi soluzione:

std::unordered_map<std::string, Edge> edges; 
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size())); 

---

La funzione che seleziona un numero casuale valida è fino a vostra scelta, ma essere sicuri che restituisce un numero nella gamma [0 ; edges.size() - 1] quando edges non è vuoto.

La funzione std::next avvolge semplicemente la funzione std::advance in un modo che consente l'assegnazione diretta.

Answer 3

Esiste un modo efficace per scegliere un Edge casuale dai bordi unordered_map?

Se per efficiente si intende O (1), quindi no, non è possibile.

Poiché gli iteratori restituiti da unordered_map::begin/end sono ForwardIterator s, gli approcci che utilizzano semplicemente std::advance sono O (n) nel numero di elementi.

Se l'uso specifico lo consente, è possibile barattare un po 'di casualità per l'efficienza:

È possibile selezionare un casuale secchio (cui si può accedere in O (1)), e poi un elemento casuale all'interno di quella secchio.

int bucket, bucket_size; 
do 
{ 
    bucket = rnd(edges.bucket_count()); 
} 
while ((bucket_size = edges.bucket_size(bucket)) == 0); 

auto element = std::next(edges.begin(bucket), rnd(bucket_size)); 

Dove rnd(n) restituisce un numero casuale nella 0, n range [).

In pratica, se si dispone di un hash decente, la maggior parte dei bucket conterrà esattamente un elemento, altrimenti questa funzione privilegerà leggermente gli elementi che sono soli nei rispettivi bucket.

Answer 4

Strict O (1) soluzione senza secchi:

1. Tenere un vettore di chiavi, quando si ha bisogno di ottenere un elemento casuale dalla mappa, selezionare una chiave casuale dal vettore e restituire valore corrispondente dal mappa - richiede tempo costante
2. Se inserisci una coppia chiave-valore nella tua mappa, controlla se tale chiave è già presente, e se non è così, aggiungi quella chiave al tuo vettore chiave - richiede tempo costante
3. Se vuoi rimuovere un elemento dalla mappa dopo che è stato selezionato, scambiare la chiave selezionata con l'elemento back() del tuo vettore chiave e chiamare pop_ indietro(), dopo che cancella l'elemento dalla mappa e restituisce il valore - richiede tempo costante

Tuttavia, vi è una limitazione: se si desidera eliminare elementi dalla mappa oltre al prelievo casuale, è necessario correggi il tuo vettore chiave, questo prende O (n) con un approccio ingenuo. Ma c'è ancora un modo per ottenere prestazioni O (1): tieni una mappa che ti dice dove si trova la chiave nel vettore chiave e aggiornala con lo scambio :)