Perché la mappa dovrebbe essere molto più veloce di unordered_map?

Question

Ho implementato un risultato di memorizzazione nella cache di ricerca costituito da chiavi di tipo State (una classe con 7 brevi valori) e valori di tipo Socre (una classe di 3 doppi). L'uso di unordered_map era almeno 20 volte più lento della mappa. Perché?

Modifica: dannatamente! La mia funzione di hash era

namespace std { 
    size_t hash<State>::operator()(State const& s) const { 
     size_t retval = hash<short>()(s.s[0]); 
     for (int i = 1; i < R; i += 2) { // 1 3 5 
      int x = (static_cast<int>(s.s[i + 1]) << 16) 
       + (static_cast<int>(s.s[i])); 
      hash_combine(retval, x); 
     } 
    } 
} 

ho dimenticato di return retval, così è stato tutto in collisione! Vorrei che unordered_map avesse una funzione hash_function_quality() che riporta il numero medio di collisioni.

Answer 1

La velocità di unordered_map è direttamente proporzionale alla velocità della funzione di hashing. Non è mai una relazione semplice. Caso in questione, se si utilizza la funzione di hashing più semplice:

std::size_t myHash(MyObjectType _object){ return 1; } 

allora che cosa ci si ritroverà con una collezione che si comporta come un elenco piuttosto che un contenitore di hash. Tutti gli oggetti verranno mappati su un singolo bucket e dovrai attraversare l'intero bucket fino a raggiungere l'oggetto desiderato (qualcosa che potrebbe richiedere O (N).)

Quello che devi fare è guardare a due cose:

1. Quale funzione di hashing stai usando? È costato un tempo ridicolo per elaborare?
2. Quante collisioni sta producendo? Cioè, quanti elementi unici vengono mappati allo stesso valore di hash?

Uno di questi può uccidere la performance.

Answer 2

std::unordered_map è in genere lento per un numero ridotto di elementi a causa della funzione hash. Richiede una quantità di tempo fissa (-ish), ma comunque una quantità significativa di tempo.

std::map d'altra parte è più semplice di std::unordered_map. Il tempo necessario per accedere a un elemento dipende dal conteggio degli elementi, ma sempre meno dal numero di elementi che cresce. E il fattore big-oh c per una std :: map è anche molto piccolo, rispetto allo std::unordered_map.

In generale, è preferibile utilizzare std::map su std::unordered_map, a meno che non si abbia un motivo specifico per utilizzare std::unordered_map. Questo vale soprattutto se non si dispone di un numero elevato di elementi.

Answer 3

unordered_map utilizza un hash table sotto il cofano, quindi la ragione più ovvia per cui hash si comporta male è perché si verificano troppe collisioni. Potresti considerare l'utilizzo di una funzione di hash diversa, non predefinita, che fornirà risultati migliori per il tuo tipo di chiavi.

Answer 4

Per

Vorrei unordered_map aveva una funzione hash_function_quality() che riporta il numero medio di collisioni.

Penso che la seguente funzione potrebbe essere utile.

unordered_map::load_factor 
    float load_factor() const; 
The member function returns the average number of elements per bucket. 

Abbassare la load_factor, meglio è la funzione di hash.