Sicher, die Suchleistung einer ungeordneten Map ist im Durchschnitt konstant und die Suchleistung einer Map ist O (logN).
Aber um ein Objekt in einer ungeordneten Map zu finden, müssen wir natürlich:
Während wir in einer Karte den gesuchten Schlüssel mit log2 (N) -Schlüsseln vergleichen müssen, ist N einfach, wenn N die Anzahl der Elemente in der Karte ist.
Ich habe mich gefragt, was der wirkliche Leistungsunterschied wäre, wenn man bedenkt, dass die Hash-Funktion Overhead hinzufügt und ein Gleichheitsvergleich nicht billiger ist als ein Vergleichsvergleich.
Anstatt die Gemeinde mit einer Frage zu belästigen, die ich selbst beantworten konnte, schrieb ich einen Test.
Ich habe die Ergebnisse unten geteilt, falls jemand anderes das interessant oder nützlich findet.
Weitere Antworten sind natürlich erwünscht, wenn jemand mehr Informationen hinzufügen kann und will.
Als Antwort auf Fragen zur Leistung in Bezug auf die Anzahl verpasster Suchen habe ich den Test überarbeitet, um dies zu parametrisieren.
Beispiel Ergebnisse:
%Vor%Taste:
%Vor%TL; DR
Ergebnisse: Die ungeordnete Karte zeigt ihre Überlegenheit, sobald Daten in der Karte vorhanden sind. Nur wenn die Karten leer sind, zeigt es eine schlechtere Leistung als die geordnete Karte.
Hier ist der neue Code:
%Vor%In diesem folgenden Test, den ich auf Apfel mit -O3 kompiliert habe, habe ich Schritte unternommen, um sicherzustellen, dass der Test fair ist, wie:
rufen Sie eine Sink-Funktion mit dem Ergebnis jeder Suche durch eine vtable auf, um zu verhindern, dass der Optimierer ganze Suchen weglegt!
führt Tests auf drei verschiedenen Arten von Karten durch, die die gleichen Daten in derselben Reihenfolge parallel enthalten. Dies bedeutet, dass, wenn ein Test anfängt "weiter zu kommen", er in das Cache-Miss-Territorium für den Suchsatz eintritt (siehe Code). Dies bedeutet, dass kein Test den unfairen Vorteil eines "heißen" Caches erleidet.
parametrieren Sie die Schlüsselgröße (und damit die Komplexität)
parametrierte die Kartengröße
hat drei verschiedene Arten von Karten getestet (die dieselben Daten enthalten) - eine ungeordnete Karte, eine Karte und einen sortierten Vektor aus Schlüssel / Wert-Paaren.
hat die Assembler-Ausgabe überprüft, um sicherzustellen, dass der Optimierer nicht in der Lage war, ganze Logikblöcke aufgrund von Dead-Code-Analysen zu optimieren.
Hier ist der Code:
%Vor%Ergebnisse:
%Vor%Wie Sie sehen, schlägt die unordered_map die Karte und den sortierten Paarvektor überzeugend. Der Vektor von Paaren ist doppelt so schnell wie die Kartenlösung. Dies ist interessant, da lower_bound und map :: at fast die gleiche Komplexität haben.
In diesem Test ist die ungeordnete Karte ungefähr dreimal so schnell (für Nachschlagewerke) wie eine geordnete Karte, und ein sortierter Vektor schlägt überzeugend eine Karte.
Ich war tatsächlich geschockt, wie viel schneller es ist.
Tags und Links c++ performance dictionary unordered-map