Gibt es einen Vorteil der Verwendung von map gegenüber unordered_map bei trivialen Schlüsseln?

Wenn Sie die Geschwindigkeit Ihrer std::map- und std::unordered_map-Implementierungen vergleichen möchten, können Sie das sparsehash -Projekt von Google verwenden, das über ein time_hash_map-Programm verfügt. Zum Beispiel mit gcc 4.4.2 auf einem x86_64-Linux-System

$ ./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)

Ich würde in etwa den gleichen Punkt wiederholen, den GMan gemacht hat: Abhängig von der Art der Verwendung kann (und ist) std::map schneller sein als std::tr1::unordered_map (unter Verwendung der in VS 2008 SP1 enthaltenen Implementierung).

Es gibt ein paar komplizierende Faktoren zu beachten. In std::map vergleichen Sie beispielsweise Schlüssel, dh, Sie sehen immer nur so viel vom Anfang eines Schlüssels, dass Sie zwischen dem rechten und dem linken Unterzweig des Baums unterscheiden können. Nach meiner Erfahrung ist es fast das einzige Mal, dass Sie einen ganzen Schlüssel betrachten, wenn Sie so etwas wie int verwenden, das Sie in einer einzigen Anweisung vergleichen können. Bei einem typischen Schlüsseltyp wie std :: string werden häufig nur wenige Zeichen verglichen.

Im Gegensatz dazu betrachtet eine anständige Hash-Funktion immer den gesamten Schlüssel. IOW, auch wenn die Tabellensuche eine konstante Komplexität aufweist, hat der Hash selbst eine annähernd lineare Komplexität (allerdings abhängig von der Länge des Schlüssels, nicht von der Anzahl der Elemente). Mit langen Zeichenfolgen als Schlüssel könnte ein std::map eine Suche beenden, bevor ein unordered_map sogar seine Suche starten würde .

Zweitens gibt es mehrere Methoden zum Ändern der Größe von Hash-Tabellen, die meisten sind jedoch ziemlich langsam - bis zu dem Punkt, dass Suchvorgänge erheblich häufiger sind als Einfügungen und Löschungen, std :: map ist oft schneller als std::unordered_map.

Natürlich können Sie, wie ich im Kommentar zu Ihrer vorherigen Frage erwähnt habe, auch eine Baumtabelle verwenden. Dies hat sowohl Vor- als auch Nachteile. Einerseits beschränkt es den schlimmsten Fall auf den eines Baumes. Es ermöglicht auch ein schnelles Einfügen und Löschen, da ich (zumindest wenn ich es getan habe) eine Tabelle mit fester Größe verwendet habe. Durch das Eliminieren aller Tabellengrößenänderungen können Sie Ihre Hash-Tabelle viel einfacher und in der Regel schneller halten.

Ein weiterer Punkt: Die Anforderungen für Hashing und baumbasierte Karten sind unterschiedlich. Das Hashing erfordert offensichtlich eine Hash-Funktion und einen Gleichheitsvergleich, bei geordneten Karten ist ein Vergleich mit weniger als erforderlich. Natürlich erfordert der erwähnte Hybrid beides. Für den üblichen Fall, dass eine Zeichenfolge als Schlüssel verwendet wird, ist dies zwar kein wirkliches Problem, aber einige Schlüsseltypen eignen sich besser zum Ordnen als zum Hashing (oder umgekehrt).

Ich war fasziniert von der Antwort von @Jerry Coffin, die darauf hindeutete, dass die geordnete Karte nach einigen Experimenten (das von Pastebin heruntergeladen werden kann) eine Leistungssteigerung auf langen Saiten aufweisen wird gilt für Sammlungen von zufälligen Zeichenfolgen: Wenn die Karte mit einem sortierten Wörterbuch initialisiert wird (das Wörter mit erheblichen Mengen an Präfix-Überlappungen enthält), bricht diese Regel zusammen, vermutlich aufgrund der erhöhten Baumtiefe, die zum Abrufen des Werts erforderlich ist. Die Ergebnisse werden unten gezeigt. Die erste Spalte ist die Einfügezeit, die zweite ist die Abrufzeit.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
[email protected]: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

Ich möchte nur darauf hinweisen, dass ... es viele Arten von unordered_maps gibt.

Schlagen Sie im Wikipedia-Artikel auf der Hash-Karte nach. Abhängig von der verwendeten Implementierung können die Merkmale in Bezug auf Nachschlagen, Einfügen und Löschen erheblich variieren.

Und das beunruhigt mich am meisten mit der Hinzufügung von unordered_map zur STL: Sie werden eine bestimmte Implementierung wählen müssen, da ich bezweifle, dass sie die Policy-Straße hinuntergehen werden, und wir werden mit einer Implementierung für den durchschnittlichen Gebrauch und festhalten nichts für die anderen Fälle ...

Zum Beispiel verfügen einige Hash-Maps über eine lineare Aufwärmfunktion, bei der, anstatt die gesamte Hash-Karte auf einmal neu zu waschen, bei jedem Einfügen ein Teil neu aufbereitet wird, was die Amortisierung der Kosten unterstützt.

Ein anderes Beispiel: Einige Hash-Maps verwenden eine einfache Liste von Knoten für einen Bucket, andere verwenden eine Map, andere verwenden keine Knoten, sondern suchen den nächstgelegenen Steckplatz. Schließlich verwenden einige eine Liste von Knoten, ordnen diese jedoch so an, dass das Element, auf das zuletzt zugegriffen wurde, neu angeordnet wird ist an der Vorderseite (wie eine Zwischenspeicherung).

Daher tendiere ich im Moment dazu, den std::map oder vielleicht einen loki::AssocVector (für eingefrorene Datensätze) zu bevorzugen.

Verstehen Sie mich nicht falsch, ich würde gerne den std::unordered_map verwenden und vielleicht auch in der Zukunft, aber es ist schwierig, der Portabilität eines solchen Containers zu "trauen", wenn Sie alle Möglichkeiten der Implementierung und der verschiedenen Leistungen in Betracht ziehen Ergebnis davon.

Hash-Tabellen haben höhere Konstanten als gewöhnliche Kartenimplementierungen, die für kleine Container von Bedeutung sind. Max Größe ist 10, 100 oder vielleicht sogar 1.000 oder mehr? Konstanten sind die gleichen wie zuvor, aber O (log n) liegt nahe bei O (k). (Denken Sie daran, dass die logarithmische Komplexität immer noch wirklich gut ist.)

Was eine gute Hash-Funktion ausmacht, hängt von den Eigenschaften Ihrer Daten ab. Wenn ich also nicht vorhabe, mir eine benutzerdefinierte Hash-Funktion anzuschauen (aber ich kann später sicherlich meine Meinung ändern, da ich fast alles in die Finger tippte) und obwohl Standardeinstellungen für viele Datenquellen anständig gewählt werden, finde ich das geordnet Die Natur der Karte genügt anfangs einer Hilfe, die ich in diesem Fall immer noch als Hash-Tabelle abbilden kann.

Auf diese Weise müssen Sie nicht einmal darüber nachdenken, eine Hash-Funktion für andere (normalerweise UDT) Typen zu schreiben, und schreiben Sie einfach op <(was Sie sowieso wollen).

Wesentliche Unterschiede, die hier nicht ausreichend erwähnt wurden:

• map hält die Iteratoren für alle Elemente stabil. In C++ 17 können Sie sogar Elemente von einer map zur anderen verschieben, ohne die ungültigen Iteratoren für sie ungültig zu machen (und wenn sie ohne potenzielle Zuweisung ordnungsgemäß implementiert wurden).
• map-Timings für einzelne Vorgänge sind normalerweise konsistenter, da sie niemals große Zuweisungen benötigen.
• unordered_map using std::hash, wie es in libstdc ++ implementiert ist, ist anfällig für DoS, wenn es mit nicht vertrauenswürdiger Eingabe gefüttert wird (es wird MurmurHash2 mit einem konstanten Seed verwendet - nicht dass Seeding wirklich helfen würde, siehe https://emboss.github.io/blog/2012/ 12/14/break-murmur-hash-flooding-dos-reloaded/ ).
• Die Bestellung ermöglicht eine effiziente Bereichsuche, z. iteriere über alle Elemente mit Schlüssel> = 42.

Ich habe kürzlich einen Test gemacht, bei dem 50000 zusammengeführt und sortiert wird. Das heißt, wenn die Zeichenfolgenschlüssel gleich sind, fügen Sie die Bytezeichenfolge zusammen. Und die endgültige Ausgabe sollte sortiert werden. Dies beinhaltet also einen Blick für jede Einfügung.

Für die map-Implementierung dauert es 200 ms, um den Job zu beenden. Für unordered_map + map dauert es 70 ms für unordered_map-Einfügung und 80 ms für map-Einfügung. Die Hybridimplementierung ist also 50 ms schneller.

Wir sollten uns überlegen, bevor wir die map verwenden. Wenn Sie nur die Daten im Endergebnis Ihres Programms sortieren müssen, ist eine Hybridlösung möglicherweise besser.

In anderen Antworten wurden Gründe angegeben. hier ist noch einer.

operationen mit std :: map (ausgeglichener binärer Baum) werden amortisiert O (log n) und Worst-Case-O (log n) . std :: unordered_map (Hashtabelle) werden amortisiert O(1) und im ungünstigsten Fall O (n).

Wie sich dies in der Praxis auswirkt, ist, dass die Hashtabelle mit einer O(n) Operation hin und wieder "hiccups" "hickcups" ist, was Ihre Anwendung möglicherweise toleriert. Wenn dies nicht tolerierbar ist, würden Sie std :: map gegenüber std :: unordered_map vorziehen.

Zusammenfassung

Angenommen, die Bestellung ist nicht wichtig:

• Wenn Sie eine große Tabelle einmal erstellen und viele Abfragen durchführen möchten, verwenden Sie std::unordered_map
• Wenn Sie eine kleine Tabelle erstellen (möglicherweise weniger als 100 Elemente) und viele Abfragen durchführen möchten, verwenden Sie std::map. Dies liegt daran, dass die Lesevorgänge O(log n) sind.
• Wenn Sie die Tabelle häufig ändern wollen, ist kann seinstd::map Eine gute Option.
• Verwenden Sie im Zweifelsfall einfach std::unordered_map.

Historischer Kontext

In den meisten Sprachen sind ungeordnete Karten (auch als Hash-basierte Wörterbücher bezeichnet) die Standardkarte, in C++ erhalten Sie jedoch eine geordnete Karte als Standardkarte. Wie ist das passiert? Einige Leute gehen fälschlicherweise davon aus, dass das C++ - Komitee diese Entscheidung in einzigartiger Weise getroffen hat, aber die Wahrheit ist leider hässlicher.

Es wird allgemein angenommen , dass C++ standardmäßig eine geordnete Karte hat, da es nicht zu viele Parameter gibt, wie sie implementiert werden können. Auf der anderen Seite gibt es bei Hash-basierten Implementierungen eine Menge zu besprechen. Um Stauungen bei der Standardisierung zu vermeiden, kamen sie gerade mit der geordneten Karte zurecht . Um 2005 hatten viele Sprachen bereits gute Implementierungen von Hash-basierten Implementierungen und so war es für das Komitee einfacher, neue std::unordered_map Zu akzeptieren. In einer perfekten Welt wäre std::map Ungeordnet und wir hätten std::ordered_map Als separaten Typ.

Leistung

Unten sollten zwei Grafiken für sich selbst sprechen ( source ):

Kleiner Zusatz zu allem oben:

Verwenden Sie map besser, wenn Sie Elemente nach Bereich abrufen müssen, da sie sortiert sind und Sie sie einfach von einer Grenze zur anderen überlaufen können.