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

Question

Ein kürzlich gehaltener Vortrag über unordered_map in C++ machte mir klar, dass ich die unordered_map für die meisten Fälle, in denen ich map zuvor wegen der Effizienz der Nachschlagefunktion ( amortisiert O(1) vs. O(log n) ). Meistens verwende ich eine Karte, entweder int o std::string als Schlüsseltyp; daher habe ich keine Probleme mit der Definition der Hash-Funktion. Je mehr ich darüber nachdachte, desto mehr wurde mir klar, dass ich keinen Grund für die Verwendung einer std::map über eine std::unordered_map im Falle von Schlüsseln mit einfachen Typen - ich habe mir die Schnittstellen angesehen und keine signifikanten Unterschiede gefunden, die sich auf meinen Code auswirken würden.

Daher die Frage: Gibt es einen wirklichen Grund für die Verwendung von std::map sur std::unordered_map im Fall von einfachen Typen wie int y std::string ?

Ich frage aus rein programmiertechnischer Sicht - ich weiß, dass es nicht ganz als Standard gilt und dass es Probleme bei der Portierung geben kann.

Außerdem erwarte ich, dass eine der richtigen Antworten lauten könnte "Es ist effizienter für kleinere Datenmengen". wegen eines geringeren Overheads (stimmt das?) - daher möchte ich die Frage auf Fälle beschränken, in denen die Anzahl der Schlüssel nicht trivial ist (>1 024).

Edit : Puh, ich habe das Offensichtliche vergessen (danke GMan!) - ja, Karten sind natürlich geordnet - das weiß ich, und ich suche nach anderen Gründen.

Answer 1

Vergessen Sie nicht, dass map hält seine Elemente geordnet. Wenn Sie das nicht aufgeben können, können Sie natürlich nicht unordered_map .

Außerdem ist zu bedenken, dass unordered_map benötigt im Allgemeinen mehr Speicherplatz. map hat nur ein paar Zeiger für die Verwaltung und Speicher für jedes Objekt. Das Gegenteil ist der Fall, unordered_map hat ein großes Array (diese können in einigen Implementierungen recht groß werden) und dann zusätzlichen Speicher für jedes Objekt. Wenn Sie Speicher-bewusst sein müssen, map sollte sich als besser erweisen, da hier das große Feld fehlt.

Wenn Sie also eine reine Nachschlagefunktion benötigen, würde ich sagen unordered_map ist der richtige Weg. Aber es gibt immer Kompromisse, und wenn man sie sich nicht leisten kann, dann kann man sie nicht nutzen.

Aus persönlicher Erfahrung kann ich sagen, dass ich eine enorme Verbesserung der Leistung (natürlich gemessen) feststellen konnte, wenn ich unordered_map anstelle von map in einer Nachschlagetabelle für die Hauptentität.

Auf der anderen Seite fand ich, dass es beim wiederholten Einfügen und Entfernen von Elementen viel langsamer war. Es ist toll für eine relativ statische Sammlung von Elementen, aber wenn Sie tun Tonnen von Einfügungen und Löschungen die Hashing + Bucketing scheint zu addieren. (Beachten Sie, dies war über viele Iterationen.)

Answer 2

Wenn Sie die Geschwindigkeit Ihrer std::map y std::unordered_map Implementierungen, können Sie Googles sparsehash Projekt, das ein time_hash_map-Programm für die Zeitmessung enthält. 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)

Answer 3

Ich schließe mich in etwa dem an, was GMan gesagt hat: Es kommt auf die Art der Nutzung an, std::map kann (und ist oft) schneller sein als std::tr1::unordered_map (unter Verwendung der in VS 2008 SP1 enthaltenen Implementierung).

Es gibt einige komplizierende Faktoren, die zu berücksichtigen sind. Zum Beispiel in std::map Sie vergleichen Schlüssel, was bedeutet, dass Sie immer nur den Anfang eines Schlüssels betrachten, um zwischen dem rechten und dem linken Unterzweig des Baums zu unterscheiden. Meiner Erfahrung nach sieht man sich fast nur dann einen ganzen Schlüssel an, wenn man etwas wie int verwendet, das man mit einer einzigen Anweisung vergleichen kann. Bei einem typischeren Schlüsseltyp wie std::string vergleicht man oft nur ein paar Zeichen oder so.

Eine anständige Hash-Funktion hingegen betrachtet immer die gesamte Taste. D.h., selbst wenn das Nachschlagen in der Tabelle eine konstante Komplexität hat, ist der Hash selbst ungefähr linear komplex (allerdings abhängig von der Länge des Schlüssels, nicht von der Anzahl der Elemente). Bei langen Zeichenketten als Schlüssel kann ein std::map könnte eine Suche beenden, bevor ein unordered_map würde sogar iniciar seine Suche.

Zweitens gibt es zwar mehrere Methoden zur Größenanpassung von Hash-Tabellen, doch sind die meisten von ihnen ziemlich langsam - bis zu dem Punkt, an dem Nachschlagen nicht mehr möglich ist. erheblich häufiger als Einfügungen und Löschungen, wird std::map oft schneller sein als std::unordered_map .

Natürlich können Sie auch eine Tabelle mit Bäumen verwenden, wie ich in meinem Kommentar zu Ihrer vorherigen Frage erwähnt habe. Dies hat sowohl Vor- als auch Nachteile. Einerseits wird der schlimmste Fall auf den eines Baumes begrenzt. Andererseits ermöglicht es ein schnelles Einfügen und Löschen, da (zumindest bei mir) eine Tabelle mit fester Größe verwendet wird. Eliminierung von tous Die Größenänderung der Tabelle ermöglicht es Ihnen, Ihre Hash-Tabelle viel einfacher und in der Regel schneller zu halten.

Ein weiterer Punkt: Die Anforderungen für Hashing und baumbasierte Karten sind unterschiedlich. Hashing erfordert offensichtlich eine Hash-Funktion und einen Gleichheitsvergleich, während geordnete Maps einen Weniger-als-Vergleich erfordern. Der von mir erwähnte Hybrid erfordert natürlich beides. Für den üblichen Fall, dass eine Zeichenkette als Schlüssel verwendet wird, ist das natürlich kein wirkliches Problem, aber manche Arten von Schlüsseln eignen sich besser zum Ordnen als zum Hashing (oder umgekehrt).

Answer 4

Ich war von der Antwort von @Jerry Coffin fasziniert, die nahelegte, dass die geordnete Karte nach einigen Experimenten Leistungssteigerungen bei langen Zeichenketten aufweisen würde (die unter pastebin ), habe ich festgestellt, dass dies nur für Sammlungen von zufälligen Zeichenfolgen zu gelten scheint. Wenn die Karte mit einem sortierten Wörterbuch initialisiert wird (das Wörter mit beträchtlichen Mengen an Präfix-Überlappungen enthält), bricht diese Regel zusammen, vermutlich wegen der erhöhten Baumtiefe, die zum Abrufen von Werten erforderlich ist. Die Ergebnisse sind unten dargestellt, die erste Zahlenspalte ist die Einfügezeit, die zweite die Abrufzeit.

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

Answer 5

Signifikante Unterschiede, die hier noch nicht hinreichend erwähnt wurden:

• map hält Iteratoren zu allen Elementen stabil, in C++17 kann man sogar Elemente von einem map auf die andere zu übertragen, ohne dass die Iteratoren zu ihnen ungültig werden (und wenn sie ordnungsgemäß implementiert sind, ohne dass eine potenzielle Zuweisung erfolgt).
• map Die Zeitvorgaben für einzelne Operationen sind in der Regel konsistenter, da sie keine großen Zuweisungen benötigen.
• unordered_map mit std::hash wie es in der libstdc++ implementiert ist, ist anfällig für DoS, wenn es mit nicht vertrauenswürdigen Eingaben gefüttert wird (es verwendet MurmurHash2 mit einem konstanten Seed - nicht dass Seeding wirklich helfen würde, siehe https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ ).
• Die Ordnung ermöglicht eine effiziente Bereichssuche, z. B. Iteration über alle Elemente mit Schlüssel 42.