Ich habe schon immer gehört, dass Vektoren schnell sind, und in meiner jahrelangen Programmiererfahrung habe ich noch nie etwas gesehen, das das zu einem Vertrag gemacht hätte. Ich entschied mich dafür, eine assoziative Klasse zu schreiben, die ein dünner Wrapper um einen sequentiellen Container war (nämlich ::std::vector und dieselbe Schnittstelle wie ::std::map zur Verfügung stellte). Der meiste Code war wirklich einfach, und ich konnte damit arbeiten kleine Schwierigkeit.
In meinen Tests mit POD-Typen unterschiedlicher Größe (4 bis 64 Byte) und std::strings mit Zählwerten zwischen acht und zweitausend war ::std::map::find jedoch schneller als mein ::associative::find , normalerweise etwa 15%. schneller, für fast alle Tests. Ich habe ein Kurzes, eigenständiges, korrektes (kompilierbares) Beispiel erstellt, das deutlich zeigt, dass bei ideone Ich habe die MSVC9-Implementierung von ::std::map::find überprüft und bestätigt, dass sie mit meinem vecfind und ::std::lower_bound -Code übereinstimmt, und kann nicht erklären, warum ::std::map::find läuft schneller, abgesehen von einer Diskussion über Stack Overflow, bei der Leute spekulierten, dass die binäre Suchmethode überhaupt nicht von der Lokalität des Vektors bis zum letzten Vergleich profitiert (was sie nicht schneller macht), und dass Zeigerarithmetik benötigt wird ::std::map Knoten benötigen es nicht und machen es langsamer.
Heute hat mich jemand dazu herausgefordert und diesen Code bei ideone bereitgestellt, was beim Testen gezeigt hat, dass der Vektor doppelt so lang ist schnell.
Wollen die Programmierer von StackOverflow mich über diese offensichtliche Diskrepanz aufklären? Ich habe beide Code-Reihen durchgegangen, und sie scheinen mir sehr ähnlich zu sein, aber vielleicht bin ich blind, weil ich so oft mit ihnen gespielt habe.
(Fußnote: Dies ist sehr nahe zu einer meiner vorherigen Fragen , aber mein Code hatte einige Fehler, die behoben wurden, aufgrund neuer Informationen / Codes, die ich für unterschiedlich genug hielt, um eine separate Frage zu begründen. Wenn nicht, werde ich daran arbeiten, sie zu verschmelzen.)
Ich sehe einige Probleme mit dem Code ( Ссылка ), den Sie auf ideone.com veröffentlicht haben. (Ideone zeigt vector tatsächlich als schneller an, aber ein lokaler Build mit der Visual Studio 11 Developer Preview zeigt map schneller an).
Zuerst habe ich die Map-Variable verschoben und sie verwendet, um den Vektor zu initialisieren, um die gleiche Elementordnung und -einheit zu erhalten, und dann gab ich lower_bound einen benutzerdefinierten Vergleicher, der nur first vergleicht, da dies Map tut. Nach diesen Änderungen zeigt Visual Studio 11 den Vektor für die gleichen 100.000 Elemente als schneller an (obwohl sich die ideone Zeit nicht wesentlich ändert). Ссылка
Mit test_size reduziert auf 8 Karte ist noch schneller. Das ist nicht verwunderlich, denn so funktioniert die Algorithmuskomplexität, alle Konstanten in der Funktion, die wirklich die Laufzeit der Materie mit kleinem N beschreiben. Ich muss test_size auf etwa 2700 erhöhen, damit der Vektor gerade und dann vorzieht Karte auf diesem System.
Was lässt Sie denken, dass mapfind() schneller ist als vecfind() ?
Der ideone-Ausgang für Ihren Code meldet ca. 50% mehr Ticks für mapfind() als für vecfind() . Wenn Sie den Code hier ausführen (x86_64 linux, g ++ - 4.5.1), dauert mapfind() etwa doppelt so lang wie vecfind() .
Wenn Sie die Karte / den Vektor um einen Faktor 10 vergrößern, erhöht sich der Unterschied auf etwa 3 ×.
Beachten Sie jedoch, dass die Summe der zweiten Komponenten unterschiedlich ist. Die Map enthält nur ein Paar mit einer gegebenen ersten Komponente (mit meiner lokalen PRNG, die eine Map mit zwei kurzen Elementen erstellt), während vector mehrere solcher Paare enthalten kann.
Die Anzahl der Elemente, die Sie in Ihren Testcontainer setzen, ist größer als die Anzahl der möglichen Ausgaben von rand() in Microsoft, daher erhalten Sie wiederholte Zahlen. Der sortierte Vektor wird alle enthalten, während der map die Duplikate auswirft. Überprüfen Sie die Größen nach dem Füllen - der Vektor wird 100000 Elemente haben, die Karte 32768. Da die Karte viel kürzer ist, wird es natürlich eine bessere Leistung haben.
Probieren Sie eine multimap für einen Apfel-zu-Äpfel-Vergleich.
Ein sortierter std :: vector hat zwei Vorteile gegenüber std :: map:
Ob diese beiden Effekte von Bedeutung sind, hängt vom Szenario ab. Es gibt zwei Faktoren, die wahrscheinlich große Auswirkungen haben:
Datentyp
Es ist ein Vorteil für den std :: vector, wenn die Elemente primitive Typen wie Integer sind. In diesem Fall hilft der Ort wirklich, da alle Daten, die für die Suche benötigt werden, sich an einem zusammenhängenden Ort im Speicher befinden.
Wenn die Elemente Saiten sind, hilft die Lokalität nicht so sehr. Der zusammenhängende Vektorspeicher speichert jetzt nur Zeigerobjekte, die möglicherweise über den gesamten Heapspeicher liegen.
Datengröße
Wenn der std :: Vektor in eine bestimmte Cache-Ebene passt, aber die std :: map nicht, hat der std :: vector einen Vorteil. Dies ist besonders der Fall, wenn Sie den Test über die gleichen Daten wiederholen.