Ist eine unordered_map wirklich schneller als eine Karte in der Praxis?
Sicher, dass die lookup-Leistung einer unordered_map ist konstant über dem Durchschnitt, und die lookup-Leistung der Karte ist O(logN).
Aber natürlich nur, um um ein Objekt zu finden in einer unordered_map, müssen wir:
- hash den Schlüssel, den wir finden wollen.
- equality_compare der Schlüssel mit jedem Schlüssel im gleichen bucket.
In der Erwägung, dass in einer Karte, müssen wir einfach less_than vergleichen Sie die gesuchten Schlüssel (mit log2(N) Schlüssel, wobei N die Anzahl der Elemente in der Karte.
Fragte ich mich, was die wirklichen performance-Unterschied wäre, gegeben, dass die hash-Funktion fügt overhead und eine equality_compare ist nicht billiger als ein less_than vergleichen.
Eher als die Mühe, die community mit einer Frage, die ich beantworten könnte, mich selbst, ich schrieb einen test.
Ich haben gemeinsam die Ergebnisse unten in den Fall, jemand anders findet dies interessant oder nützlich sind.
Weitere Antworten sind natürlich eingeladen, wenn jemand in der Lage und bereit, weitere Informationen hinzuzufügen.
- Das problem mit
map
ist nicht dielog N
per se; es ist, dass jeder memory access), wie Sie gehen, der Baum ist im wesentlichen zufällig. Dies ist nicht wichtig, wenn die Karte ist klein, aber es dominiert, wenn die Karte groß ist. (Der Unterschied zwischen dem Zugriff auf cache-und Speicher ist um eine Größenordnung oder zwei; siehe z.B. stackoverflow.com/q/4087280. Und dieser Unterschied tendenziell über CPU-Generationen, da die relevanten Physik-lokal ist.) Das gleich-zu - /kleiner-als-Operationen sind nicht wahrnehmbar sind, im Vergleich zu den Mauszeiger jagen. - Haben Sie einen Blick auf meine Testergebnisse, insbesondere die flat_map vs map. Es scheint auf den ersten Blick, dass der Zeiger jagt, die Buchhaltung für eine Verdoppelung in lookup-Zeit in eine Karte, wenn im Vergleich zu einem (großen!) sortierten Vektor. Es kann jedoch andere Faktoren spielen hierbei eine Rolle. das Geräusch scheint mehr bereit zu inline ganze Suche für
lower_bound
auf einen Vektor, alsat
für eine Karte, zum Beispiel.
Du musst angemeldet sein, um einen Kommentar abzugeben.
In der Antwort zu Fragen über Leistungen in Bezug auf die Anzahl der verpassten sucht, ich habe umgestaltet werden, den test zu parametrieren diese.
Beispiel Ergebnisse:
Schlüssel:
TL;DR
Ergebnisse: die unordered_map zeigt seine überlegenheit, sobald sich Daten in der Karte. Das einzige mal, es weist schlechtere Leistung als die bestellte Karte ist, wenn die Karten leer sind.
Hier der neue code:
In diesem folgenden test, die ich kompiliert habe, auf dem apple mit clang -O3, habe ich Schritte unternommen, um sicherzustellen, dass der test fair ist, wie:
call-Waschbecken-Funktion mit dem Ergebnis jeder Suche über eine vtable enthält, um zu verhindern, dass der Optimierer inlining gesamten Weg sucht!
tests auf 3 verschiedene Arten von Karten, mit den gleichen Daten in der gleichen Reihenfolge, in parallele. Dies bedeutet, dass, wenn ein test gestartet, um 'weiterzukommen', es beginnt die Eingabe cache-miss Gebiet für die Suche festlegen (siehe code). Dies bedeutet, dass keine test bekommt einen unfairen Vorteil der Begegnung mit einem "heißen" cache.
parametrieren Sie die Taste Größe (und damit Komplexität)
parametrisiert die Größe der Karte
getestet, drei verschiedene Arten von Karten (die gleichen Daten enthält) - eine unordered_map, eine Karte und einen sortierten Vektor, der die Schlüssel/Wert-Paaren.
überprüft die assembler-Ausgabe, um sicherzustellen, dass der Optimierer nicht in der Lage gewesen, zu optimieren away ganzen Brocken von logic durch die dead code-Analyse.
Hier ist der code:
Ergebnisse:
Wie Sie sehen können, die unordered_map überzeugend schlägt die Karte und die sortierten pair-Vektor. Die Vektor-Paare doppelt so schnell wie die Karte Lösung. Dies ist insofern interessant, als lower_bound und Karte::bei fast gleichbedeutend mit Komplexität.
TL;DR
in diesem test, der nicht sortierten Karte ist ungefähr 3 mal so schnell (für lookups) als eine geordnete map, und einen sortierten Vektor überzeugend Schlägen in der Karte.
Ich war eigentlich schockiert, wie viel schneller es ist.
nkeys
.ordered
Objekt (es sei denn, ich bin Missverständnis etwas).