Ich habe angefangen, Vergleiche zwischen:
zu machen Aber dann bemerkte ich, dass sogar auf push_back()
die Deque schneller schien. Ich muss etwas falsch machen, ich kann nicht glauben, dass ein allgemeinerer Container einen bestimmten übertreffen würde.
Mein Code mit Google Benchmark:
%Vor%Ergebnisse:
%Vor%Ich merke einige Unterschiede beim Spielen mit der Anzahl der Elemente, aber Deque übertrifft immer Vektor.
BEARBEITEN:
Compiler: gcc version 5.2.1
Kompilieren mit: g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread
Ich denke, dass -O3
tatsächlich instrumentell ist; wenn ich es ausschalte, bekomme ich eine etwas schlechtere Performance.
Ich denke, der Vektor ist langsamer, weil Sie clear()
aufrufen, was, abhängig von Ihrer STL-Implementierung, möglicherweise den zugrunde liegenden Array-Speicher freigibt.
Wenn das der Fall ist, hilft Ihr reserve()
-Aufruf nicht; und Ihr Vektor wird ständig skaliert, was erfordert, dass jedes Element in den neuen, größeren Speicher verschoben wird.
Es gibt grundsätzlich drei Kostenquellen, die beim kontinuierlichen Anhängen von Elementen an einen dynamischen Container entstehen:
Beginnen wir mit 1. vector
fragt nach dem doppelten Speicher, und deque
weist Blöcke fester Größe zu ( deque
wird normalerweise als ein Array von Arrays implementiert, wobei die Arrays der unteren Ebene eine feste Größe haben). Nach mehr Speicher zu fragen kann länger dauern, als nach weniger zu fragen, aber wenn Ihr Heap nicht sehr fragmentiert ist und Sie nach einem großen Chunk auf einmal fragen, ist das der schnellste Weg, etwas Speicher zu bekommen. Es ist wahrscheinlich schneller, ein Megabyte einmal zuzuweisen und dann 1.000 Mal nach einem Kilobyte zu fragen. Es scheint also klar zu sein, dass vector
hier den Vorteil haben wird (bis der Container so groß ist, dass er von der Fragmentierung betroffen ist). Dies ist jedoch nicht der Fall: Sie haben nur 1000 Elemente angefordert. Ich habe den folgenden Code Ссылка geschrieben. Es ist nicht sehr interessant, aber es verwendet im Grunde einen trivialen Allokator, der ein globales erhöht, um zu sehen, wie viele Zuweisungen durchgeführt werden.
vector
fragt im Rahmen Ihrer Benchmark 11-mal nach Speicher und deque
nur 10. 10. deque
fragt immer nach dem gleichen Betrag, vector
fragt nach verdoppelnden Beträgen. Außerdem muss vector
free
10 mal aufrufen. Und deque
0. Das scheint ein kleiner Gewinn für deque
zu sein.
Für interne Buchhaltung hat vector
eine einfachere Implementierung als deque
. Immerhin ist vector
nur ein dynamisches Array und deque
ist ein Array von Arrays und ist streng komplexer. Das ist also eindeutig ein Gewinn für vector
.
Schließlich Elemente für die Operationen selbst. In deque
wird nichts bewegt. Mit vector
beinhaltet jede neue Heap-Zuweisung auch das Verschieben aller Elemente. Es ist wahrscheinlich optimiert, um memcpy
für triviale Typen zu verwenden, aber es sind sogar 10 Aufrufe von memcpy
, um 1, 2, 4, 8 ... 512 Ganzzahlen zu kopieren. Dies ist eindeutig ein Gewinn für deque
.
Ich kann spekulieren, dass das Hochdrehen auf O3
sehr aggressives Inlinen von vielen der komplexeren Codepaths in deque
erlaubt, was das Gewicht von 2 reduziert. Aber natürlich, wenn Sie nicht viel detaillierter (sehr vorsichtig!) ) Benchmark, werden Sie nie sicher wissen.
Meistens soll dieser Beitrag zeigen, dass er komplexer ist als nur ein spezieller Container gegenüber einem allgemeineren Container. Ich werde jedoch eine Vorhersage machen (meinen Hals herausziehen, um sozusagen abgeschnitten zu werden): Wenn Sie die Anzahl der Elemente um einen Faktor von 2 oder 4 erhöhen, werden Sie deque
win nicht mehr sehen. Das liegt daran, dass deque
2x oder 4x so viele Heap-Zuweisungen macht, aber Vektor nur 1-2 mehr macht.
Ich kann auch hier notieren, dass deque
tatsächlich eine Art von einer ungeraden Datenstruktur ist; Es ist theoretisch ein Array von Arrays, aber in vielen Implementierungen hat das Array entweder eine bestimmte Größe oder nur ein Element, je nachdem, welches größer ist. Auch einige der großen O-Garantien sind Unsinn. push_back
ist nur konstante Zeitkonstante, da in C ++ nur Operationen an den Elementen selbst zum großen O zählen. Ansonsten sollte klar sein, dass das Array der obersten Ebene, da es sich um ein Array von Arrays handelt, proportional zur Größe ist Anzahl der bereits gespeicherten Elemente. Und schließlich hat dieses Top-Level-Array keinen Platz mehr, und Sie müssen es neu zuweisen, indem Sie O (N) -Zeiger verschieben. Also ist es nicht wirklich O (1) push_back
.