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

Einen letzten Vortrag über unordered_map in C++ machte mir klar, dass ich verwenden soll unordered_map für die meisten Fälle, wo ich map vor, weil der Wirkungsgrad von lookup ( amortisiert O(1) vs. O(log n) ). Die meisten Male, die ich eine Karte benutze ich entweder int's oder std::strings als Schlüssel, damit habe ich keine Probleme mit der definition der hash-Funktion. Je mehr ich darüber nachdachte, desto mehr kam ich zu erkennen, dass ich keine finden Grund mit einer std::map im Falle der einfachen Typen über eine unordered_map -- ich warf einen Blick auf die Schnittstellen, und fand keine signifikanten Unterschiede auswirken würden mein code.

Daher die Frage - gibt es tatsächlich einen Grund für die Verwendung std::map über unordered map im Falle der einfachen Typen wie int und std::string?

Ich verlange von einem streng Standpunkt der Programmierung-ich weiß, dass es nicht komplett als standard, und es kann zu Problemen mit der Portierung.

Ich auch erwarten, dass einem die richtigen Antworten sein könnten "es ist effizienter für kleinere Datenmengen"weil ein kleiner overhead (stimmt das?) - daher möchte ich beschränken, die Frage zu Fällen, in denen die Anzahl der keys ist nicht-trivial (>1 024).

Edit: duh, ich vergaß das offensichtliche (danke GMan!) -- ja, Karte ist bestellt, natürlich-ich weiß, dass, und bin auf der Suche nach anderen Gründen.

InformationsquelleAutor der Frage Kornel Kisielewicz | 2010-02-04

  1. 324

    Vergessen Sie nicht, die map's halten Ihre Elemente bestellt. Wenn Sie nicht aufgeben, denn Sie kann nicht mit einem unordered_map.

    Etwas anderes im Auge zu behalten ist, dass unordered_map's in der Regel mehr Arbeitsspeicher verwenden. Ein map muss nur ein paar house-keeping Zeiger dann Speicher für jedes Objekt. Im Gegenteil, unordered_map's haben eine große Auswahl (dieser kann ziemlich groß in einigen Implementierungen) und dann zusätzlichen Speicher für jedes Objekt. Wenn Sie brauchen, um Speicher-aware, ein map sollte besser beweisen, weil es an der großen Auswahl.

    Also, wenn Sie brauchen, Reine lookup-retrieval, ich würde sagen, ein unordered_map ist der Weg zu gehen. Aber es gibt immer trade-offs, und wenn Sie sich nicht leisten können, dann können Sie es nicht verwenden.

    Nur aus eigener Erfahrung, fand ich eine enorme Verbesserung in der Leistung (gemessen natürlich) bei Verwendung eines unordered_map statt einer map im Haupt-entity-look-up-Tabelle.

    Auf der anderen Seite, ich fand es war viel langsamer wiederholt einfügen und entfernen von Elementen. Es ist toll für eine relativ statische Gruppe von Elementen, aber wenn Sie tun, Tonnen von Einfügungen und Löschungen der hashing + giesst scheint zu addieren. (Beachten Sie, dies wurde über viele Iterationen.)

    InformationsquelleAutor der Antwort GManNickG

  2. 104

    Wenn Sie wollen, vergleichen Sie die Geschwindigkeit der std::map und std::unordered_map-Implementierungen, die Sie verwenden könnte Google sparsehash Projekt, das eine time_hash_map Programm zur Zeit. 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)

    InformationsquelleAutor der Antwort Blair Zajac

  3. 67

    Ich würde echo etwa der gleichen Stelle GMan aus: je nach Art der Nutzung, std::map werden kann (und oft ist) schneller als std::tr1::unordered_map (mit der Umsetzung enthalten in VS 2008 SP1).

    Gibt es ein paar erschwerenden Faktoren im Auge zu behalten. Zum Beispiel, in std::map Sie sind Vergleich-Schlüssel, was bedeutet, dass Sie immer nur anschauen, genug der Anfang des Schlüssels zu unterscheiden zwischen den rechten und linken sub-Zweige des Baumes. In meiner Erfahrung, fast die einzige Zeit, die Sie Blick auf einen ganzen Schlüssel ist, wenn Sie so etwas wie int, die Sie vergleichen können in einer einzigen Instruktion. Mit einem typischen Schlüssel-Typ wie std::string, Sie oft zu vergleichen, nur ein paar Zeichen oder so.

    Eine anständige hash-Funktion, durch Kontrast, sieht immer am gesamte - Taste. IOW, auch wenn die lookup-Tabelle ist die Konstante Komplexität, den hash selbst hat annähernd lineare Komplexität (obwohl auf der Länge der Schlüssel, nicht die Anzahl der Elemente). Mit langen strings als Schlüssel, ein std::map vielleicht beenden Sie eine Suche durch, bevor ein unordered_map würde sogar start die Suche.

    Sekunde, während es gibt mehrere Methoden zum ändern der Größe, hash-Tabellen, die meisten von Ihnen sind ziemlich langsam-bis zu dem Punkt, es sei denn, lookups sind deutlich häufiger als Insertionen und Deletionen, std::map werden oft schneller als std::unordered_map.

    Natürlich, wie ich bereits im Kommentar zu Ihrer vorherigen Frage, Sie können auch eine Tabelle von Bäumen. Dies hat sowohl Vorteile als auch Nachteile. Einerseits begrenzt es die schlimmsten Fall zu einem Baum. Es ermöglicht auch das schnelle einfügen und löschen, da (zumindest wenn ich es getan habe) ich habe eine Feste Größe der Tabelle. Die Beseitigung alle Tabelle Größenänderung ermöglicht es Ihnen, um Ihre hash-Tabelle viel einfacher und in der Regel schneller.

    Edit: Oops, ich vergaß fast zu erwähnen, ein weiterer Punkt: die Anforderungen für die Hash-und tree-basierten Karten sind unterschiedlich. Hashing erfordert natürlich eine hash-Funktion, und ein Geschlechter-Vergleich, wo die bestellten Karten benötigen eine weniger-als-Vergleich. Natürlich sind die Hybriden, die ich erwähnt erfordert. Natürlich, für den Allgemeinen Fall mit einem string als key, das ist nicht wirklich ein problem, aber einige Arten von Schlüsseln Anzug bestellen besser als das hashing (oder Umgekehrt).

    InformationsquelleAutor der Antwort Jerry Coffin

  4. 46

    Ich war fasziniert von der Antwort von @Jerry Sarg, die vorgeschlagen, dass die bestellte Karte würde zeigen performance-Steigerung auf lange Zeichenfolgen, nach einigen Experimenten (die kann heruntergeladen werden von pastebin), ich habe festgestellt, dass dies scheint nur zu halten gilt für Sammlungen von zufälligen Zeichenfolgen, wenn die Karte initialisiert wird mit einer sortierten Wörterbuch (welche Wörter enthalten, mit erheblichen Mengen von Präfix-überlappung), diese Regel bricht, vermutlich wegen der erhöhten Baum Tiefe erforderlich zum abrufen von Wert. Die Ergebnisse sind unten dargestellt, wird der 1. Spalte "Nummer" ist, legen die Zeit, 2. ist die fetch-Zeit.

    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

    InformationsquelleAutor der Antwort Gearoid Murphy

  5. 27

    Möchte ich noch anmerken, dass... es gibt viele Arten von unordered_maps.

    Suchen die Wikipedia-Artikel auf hash-map. Je nachdem, welche Implementierung verwendet wurde, werden die Merkmale Laufzeit der look-up, Einfügung und Löschung variieren ganz erheblich.

    Und das ist es, was mich beunruhigt, die mit dem Zusatz von unordered_map auf die STL: Sie haben die Wahl einer besonderen Umsetzung, da ich bezweifle, dass Sie werde gehen Sie Policy Straße, und so werden wir das fest mit einer Umsetzung für den durchschnittlichen Gebrauch, und nichts für die anderen Fälle...

    Beispielsweise einige hash-maps-linearen Aufwärmen, wo anstelle der Aufbereitung die ganze hash map auf einmal, ein Teil ist sofort wieder bei jeder Einfügung, die hilft bei der Amortisation der Kosten.

    Anderes Beispiel: einige hash-maps verwenden, die eine einfache Liste von Knoten für einen Eimer, der andere eine Karte, andere verwenden Sie nicht Knoten, sondern finden den nächsten slot und schließlich einige werden eine Liste von Knoten, sondern ordnen es so, dass die zuletzt aufgerufenen element ist an der Vorderseite (wie eine caching-Sache).

    Also im moment tendiere ich dazu, lieber das std::map oder vielleicht ein loki::AssocVector (für die Tiefkühl-Datensätze).

    Versteh mich nicht falsch, ich möchte die std::unordered_map und ich kann in die Zukunft, aber es ist schwer "Vertrauen", die übertragbarkeit solcher container, wenn Sie denken Sie an all die Möglichkeiten, es umzusetzen und die verschiedenen Darbietungen, die Ergebnis dieser.

    InformationsquelleAutor der Antwort Matthieu M.

  6. 14

    Hash-Tabellen haben eine höhere Konstanten als gemeinsame map-Implementierungen, die eine bedeutsame Rolle für kleine Behälter. Max Größe ist 10, 100 oder vielleicht sogar 1000 oder mehr? Konstanten sind die gleichen wie immer, aber O(log n) ist in der Nähe der O(k). (Denken Sie daran logarithmische Komplexität ist immer noch wirklich gut.)

    Was macht eine gute hash-Funktion hängt von Ihren Daten Eigenschaften; so, wenn ich nicht plan auf der Suche in einem benutzerdefinierten hash-Funktion (kann aber durchaus meine Meinung ändern später, und einfach da ich typedef verdammt in der Nähe alles) und obwohl die Standardwerte sind so gewählt, führen Sie anständig für viele Daten-Quellen, ich finde die bestellte Art der Karte zu sein genug, eine Hilfe am Anfang, dass ich noch die Standard-map eher als eine hash-Tabelle in diesem Fall.

    Plus so dass Sie nicht haben, um sogar zu denken, über das schreiben einer hash-Funktion für andere (in der Regel UDT) Typen, und schreiben Sie einfach op< (was Sie sowieso wollen).

    InformationsquelleAutor der Antwort

  7. 9

    Habe ich einen test vor kurzem, das macht 50000 merge&Sortieren. Das bedeutet, dass, wenn die string-keys sind die gleichen, Zusammenführen der byte-string. Und die endgültige Ausgabe sortiert werden soll. So schließt dies eine look-up-für jeden einsetzen.

    Für die map Umsetzung, es dauert 200 ms, um den job zu beenden. Für die unordered_map + map es dauert 70 ms für unordered_map einfügen und 80 ms für map einsetzen. So ist die hybride Umsetzung ist 50 ms schneller.

    Sollten wir zweimal überlegen bevor wir die map. Wenn Sie nur die Daten, die sortiert werden in das endgültige Ergebnis ist Ihr Programm, eine hybrid-Lösung besser sein könnte.

    InformationsquelleAutor der Antwort wendong

  8. 9

    Erhebliche Unterschiede, die nicht wirklich angemessen hier erwähnt:

    • map hält Iteratoren alle Elemente, stabile, in C++17 können Sie auch Elemente verschieben von einem map zu den anderen, ohne ungültig, ungültig, Iteratoren, um Sie (und wenn Sie richtig umgesetzt ohne mögliche Zuordnung).
    • map timings für die einzelnen Operationen sind in der Regel mehr im Einklang, da Sie nie brauchen große Zuweisungen.
    • unordered_map mit std::hash umgesetzt, in die libstdc++ ist anfällig für DoS, wenn gefüttert eine nicht Vertrauenswürdige Eingabe (es verwendet MurmurHash2 mit einem Konstanten seed - nicht, dass das seeding wirklich helfen würde, siehe https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/).
    • Bestellt ermöglicht eine effiziente Auswahl sucht, z.B. iterieren über alle Elemente mit key >= 42.

    InformationsquelleAutor der Antwort user1531083

  9. 7

    Gründe wurden in anderen Antworten; hier ist eine andere.

    std::map (balanced binary tree) Operationen amortisiert O(log n) und im schlechtesten Fall O(log n).
    std::unordered_map (hash-Tabelle) Operationen amortisiert O(1) und worst-case O(n).

    Wie diese spielt sich in der Praxis, dass die hash-Tabelle "Schluckauf" jeder einmal in eine Weile mit einem O(n) - operation, die möglicherweise oder möglicherweise nicht etwas sein, was Ihre Anwendung tolerieren kann. Wenn Sie können nicht dulden, Sie würden lieber std::map über std::unordered_map.

    InformationsquelleAutor der Antwort Don Hatch

  10. -1

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

    "Intern werden die Elemente in einer map sind immer sortiert nach Ihrem Schlüssel nach einer bestimmten strict weak ordering Kriterium gekennzeichnet durch seine internen Vergleich-Objekt (Typ Vergleichen).

    map-Container sind in der Regel langsamer als Container unordered_map, um den Zugriff auf die einzelnen Elemente nach Ihren Schlüssel, aber Sie erlauben die direkte iteration auf Teilmengen basierend auf Ihrer Bestellung".

    InformationsquelleAutor der Antwort Kunal Bansal

Schreibe einen Kommentar