C’è qualche vantaggio nell’usare la mappa su unordered_map in caso di chiavi triviali?

Un recente discorso su unordered_map in C ++ mi ha fatto capire che dovrei usare unordered_map per la maggior parte dei casi in cui ho usato map precedenza, a causa dell’efficienza della ricerca ( O (1) contro O (log n) ). La maggior parte delle volte che uso una mappa uso sia int ‘s che std::strings come chiavi, quindi non ho problemi con la definizione della funzione hash. Più ci pensavo, più mi rendevo conto che non riesco a trovare alcun motivo per usare una std::map in caso di tipi semplici su una mappa unordered_map – Ho dato un’occhiata alle interfacce e non ho trova eventuali differenze significative che potrebbero avere un impatto sul mio codice.

Da qui la domanda: c’è qualche ragione per usare std::map su una unordered map in caso di tipi semplici come int e std::string ?

Lo sto chiedendo da un punto di vista strettamente programmatico: so che non è completamente considerato standard e che potrebbe porre problemi con il porting.

Inoltre mi aspetto che una delle risposte corrette potrebbe essere “è più efficiente per insiemi di dati più piccoli” a causa di un overhead più piccolo (è vero?) – quindi mi piacerebbe limitare la domanda ai casi in cui la quantità di chiavi è non banale (> 1 024).

Edit: duh, ho dimenticato l’ovvio (grazie GMan!) – sì, le mappe sono ordinate naturalmente – Lo so, e sto cercando altre ragioni.

Non dimenticare che la map mantiene i loro elementi ordinati. Se non puoi rinunciare a quello, ovviamente non puoi usare una mappa unordered_map .

Qualcos’altro da tenere a mente è che la mappa unordered_map utilizza generalmente più memoria. Una map ha solo alcuni indicatori di casa e quindi la memoria per ogni object. Al contrario, unordered_map ha un grande array (che può essere abbastanza grande in alcune implementazioni) e quindi una memoria aggiuntiva per ogni object. Se devi essere consapevole della memoria, una map dovrebbe dimostrarsi migliore, perché manca la grande matrice.

Quindi, se hai bisogno di un lookup-retrieval puro, direi che una mappa unordered_map è la strada da percorrere. Ma ci sono sempre dei compromessi, e se non puoi permetterteli, allora non puoi usarli.

Proprio dall’esperienza personale, ho riscontrato un enorme miglioramento delle prestazioni (misurato, ovviamente) quando si utilizza una mappa unordered_map invece di una map in una tabella di ricerca di entity framework principali.

D’altra parte, ho scoperto che era molto più lento a inserire e rimuovere ripetutamente elementi. È fantastico per una raccolta di elementi relativamente statica, ma se stai facendo tonnellate di inserimenti e cancellazioni sembra che l’hashing + bucketing si sommi. (Nota, questo era su molte iterazioni).

Se vuoi confrontare la velocità delle implementazioni std :: map e std :: unordered_map, puoi utilizzare il progetto sparsehash di Google che ha un programma time_hash_map per cronometrare. Ad esempio, con gcc 4.4.2 su un sistema Linux x86_64

 $ ./time_hash_map TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations): map_grow 126.1 ns (27427396 hashes, 40000000 copies) 290.9 MB map_predict/grow 67.4 ns (10000000 hashes, 40000000 copies) 232.8 MB map_replace 22.3 ns (37427396 hashes, 40000000 copies) map_fetch 16.3 ns (37427396 hashes, 40000000 copies) map_fetch_empty 9.8 ns (10000000 hashes, 0 copies) map_remove 49.1 ns (37427396 hashes, 40000000 copies) map_toggle 86.1 ns (20000000 hashes, 40000000 copies) STANDARD MAP (4 byte objects, 10000000 iterations): map_grow 225.3 ns ( 0 hashes, 20000000 copies) 462.4 MB map_predict/grow 225.1 ns ( 0 hashes, 20000000 copies) 462.6 MB map_replace 151.2 ns ( 0 hashes, 20000000 copies) map_fetch 156.0 ns ( 0 hashes, 20000000 copies) map_fetch_empty 1.4 ns ( 0 hashes, 0 copies) map_remove 141.0 ns ( 0 hashes, 20000000 copies) map_toggle 67.3 ns ( 0 hashes, 20000000 copies) 

Vorrei echeggiare all’incirca lo stesso punto di GMan: a seconda del tipo di utilizzo, std::map può essere (e spesso è) più veloce di std::tr1::unordered_map (utilizzando l’implementazione inclusa in VS 2008 SP1).

Ci sono alcuni fattori complicanti da tenere a mente. Ad esempio, in std::map , stai confrontando le chiavi, il che significa che guardi sempre e solo l’inizio di una chiave per distinguere tra i rami secondari destro e sinistro dell’albero. Nella mia esperienza, quasi l’unica volta in cui guardi un’intera chiave è se stai usando qualcosa di simile a int che puoi confrontare in una singola istruzione. Con un tipo di chiave più tipico come std :: string, si confrontano spesso solo pochi caratteri.

Una funzione di hash decente, al contrario, guarda sempre l’ intera chiave. IOW, anche se la ricerca della tabella è una complessità costante, l’hash stesso ha una complessità approssimativamente lineare (sebbene sulla lunghezza della chiave, non sul numero di elementi). Con le stringhe lunghe come chiavi, una std::map potrebbe terminare una ricerca prima che una unordered_map possa iniziare la sua ricerca.

Secondo, mentre ci sono diversi metodi per ridimensionare le tabelle hash, la maggior parte di esse è piuttosto lenta – al punto che a meno che le ricerche siano molto più frequenti di inserzioni e cancellazioni, std :: map sarà spesso più veloce di std::unordered_map .

Naturalmente, come ho detto nel commento alla tua domanda precedente, puoi anche usare una tabella di alberi. Questo ha sia vantaggi che svantaggi. Da un lato, limita il caso peggiore a quello di un albero. Permette anche l’inserimento rapido e la cancellazione, perché (almeno quando l’ho fatto) ho usato una tabella di dimensioni fisse. L’eliminazione di tutti i ridimensionamenti delle tabelle consente di mantenere la tabella hash molto più semplice e in genere più veloce.

Modifica: Oops, ho quasi dimenticato di menzionare un altro punto: i requisiti per l’hashing e le mappe ad albero sono diversi. L’hashing richiede ovviamente una funzione hash e un confronto di uguaglianza, in cui le mappe ordinate richiedono un confronto inferiore. Ovviamente l’ibrido che ho citato richiede entrambi. Naturalmente, per il caso comune di usare una stringa come chiave, questo non è davvero un problema, ma alcuni tipi di chiavi si adattano meglio all’ordinamento (o viceversa).

Sono rimasto affascinato dalla risposta di @Jerry Coffin, che ha suggerito che la mappa ordinata avrebbe esibito aumenti delle prestazioni su stringhe lunghe, dopo alcuni esperimenti (che possono essere scaricati da pastebin ), ho trovato che questo sembra essere vero solo per le collezioni di stringhe casuali, quando la mappa viene inizializzata con un dizionario ordinato (che contiene parole con notevoli quantità di prefisso-sovrapposizione), questa regola si interrompe, presumibilmente a causa della maggiore profondità dell’albero necessaria per recuperare il valore. I risultati sono mostrati sotto, la colonna del primo numero è l’ora di inserimento, la seconda è il tempo di recupero.

 g++ -g -O3 --std=c++0x -c -o stdtests.o stdtests.cpp g++ -o stdtests stdtests.o gmurphy@interloper:HashTests$ ./stdtests # 1st number column is insert time, 2nd is fetch time ** Integer Keys ** unordered: 137 15 ordered: 168 81 ** Random String Keys ** unordered: 55 50 ordered: 33 31 ** Real Words Keys ** unordered: 278 76 ordered: 516 298 

Vorrei solo sottolineare che … ci sono molti tipi di file unordered_map .

Cerca l’ articolo di Wikipedia sulla mappa hash. A seconda dell’implementazione utilizzata, le caratteristiche in termini di ricerca, inserimento e cancellazione potrebbero variare in modo significativo.

Ed è quello che mi preoccupa di più con l’aggiunta di unordered_map all’STL: dovranno scegliere una particolare implementazione poichè dubito che scenderanno la Policy road, e quindi saremo bloccati con un’implementazione per l’uso medio e niente per gli altri casi …

Ad esempio alcune mappe hash hanno un rehashing lineare, in cui invece di rimettere a punto l’intera mappa hash in una volta, una porzione è rehash ad ogni inserimento, che aiuta ad ammortizzare il costo.

Un altro esempio: alcune mappe hash usano un semplice elenco di nodes per un bucket, altri usano una mappa, altri non usano i nodes ma trovano lo slot più vicino e infine alcuni useranno un elenco di nodes ma lo riordineranno in modo che l’ultimo elemento acceduto è davanti (come una cosa di cache).

Quindi al momento tendo a preferire la std::map o forse un loki::AssocVector (per i set di dati congelati).

Non fraintendermi, mi piacerebbe usare la std::unordered_map e potrei farlo in futuro, ma è difficile “fidarsi” della portabilità di un tale contenitore quando si pensa a tutti i modi di implementarlo e varie prestazioni che risultano da questo.

Le tabelle hash hanno costanti più elevate rispetto alle comuni implementazioni di mappe, che diventano significative per i piccoli contenitori. La dimensione massima è 10, 100, o forse anche 1.000 o più? Le costanti sono le stesse di sempre, ma O (log n) è vicino a O (k). (Ricorda che la complessità logaritmica è ancora molto buona).

Ciò che rende una buona funzione di hash dipende dalle caratteristiche dei tuoi dati; quindi se non ho intenzione di guardare una funzione hash personalizzata (ma posso sicuramente cambiare idea più tardi, e facilmente dato che mi digerisco praticamente vicino a tutto) e anche se i valori predefiniti sono scelti per eseguire decentemente per molte fonti di dati, trovo l’ordine la natura della mappa per essere abbastanza di un aiuto inizialmente che io continuo a mappare in modo predefinito piuttosto che una tabella hash in quel caso.

In più in questo modo non devi nemmeno pensare di scrivere una funzione di hash per altri tipi (di solito UDT), e basta scrivere op < (che vuoi comunque).

Differenze significative che non sono state adeguatamente menzionate qui:

  • map mantiene gli iteratori a tutti gli elementi stabili, in C ++ 17 puoi persino spostare elementi da una map all’altra senza invalidare iteratori invalidanti (e se correttamente implementati senza alcuna allocazione potenziale).
  • map tempi delle map per le singole operazioni sono in genere più coerenti, poiché non richiedono mai allocazioni di grandi dimensioni.
  • unordered_map usando std::hash come implementato in libstdc ++ è vulnerabile a DoS se alimentato con input non fidato (usa MurmurHash2 con un seme costante – non che il seeding sarebbe davvero d’aiuto, vedere https://emboss.github.io/blog/2012 / 12/14 / breaking-murmur-hash-flooding-dos-reloaded / ).
  • Essere ordinati consente ricerche di intervalli efficienti, ad es. Iterare su tutti gli elementi con il tasto> = 42.

Di recente ho eseguito un test che rende 50000 unisci e ordina. Ciò significa che se le chiavi della stringa sono uguali, unire la stringa di byte. E l’output finale dovrebbe essere ordinato. Quindi questo include una ricerca per ogni inserimento.

Per l’implementazione della map , ci vogliono 200 ms per completare il lavoro. Per la map unordered_map +, ci vogliono 70 ms per l’inserimento unordered_map e 80 ms per l’inserimento della map . Quindi l’implementazione ibrida è più veloce di 50 ms.

Dovremmo pensarci due volte prima di usare la map . Se hai solo bisogno di ordinare i dati nel risultato finale del tuo programma, una soluzione ibrida potrebbe essere migliore.

Le ragioni sono state date in altre risposte; ecco un altro

Le operazioni std :: map (albero binario bilanciato) sono ammortizzate O (log n) e worst case O (log n). std :: unordered_map (hash table) le operazioni sono ammortizzate O (1) e peggiore caso O (n).

Il modo in cui questo si verifica in pratica è che la tabella hash “singhiozza” di tanto in tanto con un’operazione O (n), che può o non può essere qualcosa che la tua applicazione può tollerare. Se non può tollerarlo, preferiresti std :: map su std :: unordered_map.

Nella maggior parte delle lingue, la mappa non ordinata (ovvero i dizionari basati su hash) sono la mappa predefinita, tuttavia in C ++ viene ordinata la mappa come mappa predefinita. Come è successo? Alcune persone ritengono erroneamente che la commissione C ++ abbia preso questa decisione nella loro saggezza unica, ma la verità è purtroppo più brutta di quella.

È opinione diffusa che C ++ finisca con la mappa ordinata come predefinita perché non ci sono troppi parametri su come possono essere implementati. D’altra parte, le implementazioni basate su hash hanno un sacco di cose di cui parlare. Quindi, per evitare i grovigli nella standardizzazione, sono appena andati d’accordo con la mappa ordinata. Intorno al 2005, molte lingue avevano già una buona implementazione di implementazione basata su hash e quindi era più facile per il comitato accettare la nuova std::unordered_map . In un mondo perfetto, std::map sarebbe stato ordinato e avremmo std::ordered_map come tipo separato.

Sotto due grafici dovrebbero parlare da soli ( fonte ):

inserisci la descrizione dell'immagine qui

inserisci la descrizione dell'immagine qui

Sommario

Supponendo che l’ordine non sia importante:

  • Se hai intenzione di creare una tabella di grandi dimensioni una volta e fare molte query, usa std::unordered_map
  • Se stai per build una piccola tabella (può essere inferiore a 100 elementi) e fare molte query, usa std::map . Questo perché le letture su di esso sono O(log n) .
  • Se cambierai molto tavolo allora potrebbe essere std::map è una buona opzione.
  • Se sei in dubbio, usa semplicemente std::unordered_map .

Piccola aggiunta a tutti sopra:

Meglio usare la map , quando è necessario ottenere elementi per intervallo, poiché vengono ordinati e si può semplicemente scorrere su di essi da un confine all’altro.

Da: http://www.cplusplus.com/reference/map/map/

“Internamente, gli elementi in una mappa sono sempre ordinati per la sua chiave seguendo uno specifico severo criterio di ordinamento debole indicato dal suo object di confronto interno (di tipo Compare).

I contenitori di mappe sono generalmente più lenti dei contenitori unordered_map per accedere ai singoli elementi tramite la loro chiave, ma consentono l’iterazione diretta su sottoinsiemi in base al loro ordine. ”