hash_map und Karte, die schneller ist? weniger als 10000 Stück
vs2005 Unterstützung
::stdext::hash_map
::std::map.
doch wie es scheint ::stdext::hash_map ist das einfügen und entfernen OP langsamer ist, dann ::std::map in meinem test.
( weniger als 10.000 Elemente)
Interessant....
Kann jemand offored einen Vergleich-Artikel über Sie?
- VS2005 ist hash_map ist schrecklich ineffizient mit std::string ' s..., was sind Sie hashing?
- Ich legte shared_ptr<XXX> in
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es nicht nur um das einsetzen und entfernen. Sie müssen Bedenken, dass Speicher zugewiesen ist anders in einer hash_map vs Landkarte und Sie jedes mal zur Berechnung des Hashs der Wert, nach dem gesucht wird.
Ich denke, das Dr. Dobbs Artikel werden die Antwort auf Ihre Frage am besten:
C++ STL Hash-Behälter und Leistung
Normalerweise Sie schauen, um die Komplexität der verschiedenen Vorgänge, und das ist eine gute Anleitung: amortisiert O(1) insert O(1) lookup, delete für eine hashmap als gegen O(log N) insert, lookup, delete für eine Baum-basierte Karte.
Allerdings gibt es bestimmte Situationen, wo die Schwierigkeiten sind irreführend, weil die Konstanten Bedingungen beteiligt sind extrem. Angenommen, Ihre 10k Elemente sind kodiert, aus strings. Nehmen wir weiter an, dass diese Saiten sind jeweils 100k Zeichen lang sein. Nehme an, dass die verschiedenen Saiten in der Regel unterscheiden sich in der Nähe der Anfang der Zeichenfolge (zum Beispiel, wenn Sie sind im wesentlichen zufällig, Paare unterscheiden sich in das erste byte mit einer Wahrscheinlichkeit von 255/256).
Dann zu tun, eine Suche die hashmap hat hash-100k-string. Das ist O(1) in der Größe der Sammlung, aber es könnte sehr lange dauern, da es wahrscheinlich O(M) in der Länge der Zeichenfolge. Eine ausgewogene Struktur zu tun hat log N <= 14 Vergleiche, aber jede braucht man nur ein paar bytes. Das könnte nicht sehr lange überhaupt.
In Bezug auf Speicher zugreifen, der mit einem 64 byte cache-line Größe, die hashmap lädt über 1500 sequentielle Linien, und nicht 100k byte-Operationen, in der Erwägung, dass der Baum lädt 15 zufällige Linien (eigentlich wohl 30 wegen dem Umweg über den string) und nicht 14 * (einige kleine Zahl) byte Operationen. Sie können sehen, dass die ehemaligen könnte gut sein, die langsamer sind als die letzteren. Oder es könnte schneller gehen: wie gut sind Ihre Architektur, der FSB-Bandbreite, stall, Zeit, und spekulative read-caching?
Wenn der Nachschlagetabelle eine übereinstimmung findet, dann natürlich neben diesen beiden Strukturen brauchen, um einen einzigen full-length-string-Vergleich. Auch die hashmap tun könnten weitere ausgefallene Vergleiche, wenn es geschieht, um eine Kollision im Eimer.
Also unter der Annahme, dass fehlgeschlagene Vergleiche sind so schnell als vernachlässigbar gering sein, während erfolgreiche Vergleiche und hashing-ops sind langsam, der Baum könnte ungefähr 1.5-2 mal schneller als der hash. Wenn diese Annahmen nicht halten, dann wird es nicht sein.
Ein extremes Beispiel, natürlich, aber es ist ziemlich leicht zu sehen, dass auf Ihre Daten, insbesondere die O(log N) - operation möglicherweise wesentlich schneller als eine bestimmte O(1) - operation. Sie sind natürlich Recht testen wollen, aber wenn Sie Ihre test-Daten ist nicht repräsentativ für die Reale Welt, dann wird Ihr test-Ergebnisse können nicht repräsentativ sein, entweder. Vergleiche der Daten-Strukturen basierend auf der Komplexität beziehen sich auf das Verhalten im Grenzwert N gegen unendlich. Aber N nicht ins unendliche Streben. Es ist 10000.
Es hängt davon ab, Ihre Nutzung und Ihre hash-Kollisionen. Ist ein binärer Baum und der andere ist ein hashtable.
Idealerweise wird die hash-map wird O(1) einfügen und nachschlagen, und die map O(ln n), aber es geht nicht-aufeinander-hashes.
hash_map verwendet eine hash-Tabelle, etwas, das bietet nahezu konstanter Zeit O(1) Operationen, vorausgesetzt, dass eine gute hash-Funktion.
Karte verwendet eine BST, bietet es O(lg(n)) Operationen, für 10000 Elemente, die 13, die ist sehr akzeptabel
Ich würde sagen, bleiben Sie mit der Karte, es ist sicherer.
Hash-Tabellen sollen schneller sein als binäre Bäume (also std::map) für die Suche. Niemand hat jemals vorgeschlagen, dass Sie schneller für einfügen und löschen.
Einer hash-map erstellen einen hash des Strings/der Schlüssel für die Indizierung. Obwohl während der Nachweis der Komplexität es wird erwähnt, dass O(1), hash_map hat Kollisionserkennung für jede insert -, wie ein hash-Wert kann eine Zeichenfolge erzeugen, die denselben index wie der hash-Wert von einer anderen Zeichenfolge. Eine hash map, damit Komplexität für die Verwaltung von Kollisionen & Sie wissen, dass diese Kollisionen sind auf der Grundlage der input-Daten.
Allerdings, wenn Sie gehen zu erfüllen sind viele look-ups auf die Struktur, entscheiden Sie sich für hash_map.