Ich finde nur heraus, dass Standard-Std-Deque wirklich langsam ist, wenn ich mit meiner "hausgemachten" Version von Stacks vergleiche, die vorher zugewiesene Arrays verwenden.
Das ist Code meines Stapels:
.
Ich führe diesen einfachen Benchmark für deque:
.
Verwendung von Std-Stack mit Vektor als Container (wie 'Michael Kohne' vorgeschlagen)
.
Und das gleiche für meinen FastStack:
.
Die Ergebnisse nach 4 Läufen sind wie folgt:
Deque 15.529
Deque 15.3756
Deque 15.429
Deque 15.4778
Stapel 6.19099
Stapel 6.1834
Stapel 6.19315
Stapel 6.19841
FastStack 3.01085
FastStack 2.9934
FastStack 3.02536
FastStack 3.00937
Die Ergebnisse sind in Sekunden und ich habe den Code auf Intel i5 3570k (auf Standard-Uhr) ausgeführt. Ich habe den VS2010-Compiler mit allen verfügbaren Optimierungen verwendet.
Ich weiß, dass mein FastStack viele Einschränkungen hat, aber es gibt viele Situationen, in denen es verwendet werden könnte und wenn es einen schönen Schub geben kann! (Ich habe es in einem Projekt verwendet, wo ich im Vergleich zu std :: queue zweimal schneller bin.)
So, jetzt ist meine Frage:
Gibt es irgendwelche anderen "Hemmnisse" in C ++, die jeder benutzt, aber niemand weiß von ihnen?
EDIT: Ich möchte nicht beleidigend sein, ich bin nur neugierig, wenn du unbekannte "Beschleunigungen" wie diese kennst.
Sie vergleichen Äpfel und Orangen. Die Dequeue ist DOUBLE-ENDED, was erfordert, dass sie intern ein wenig anders ist als der einfache Stack, den Sie implementiert haben. Versuchen Sie stattdessen, Ihren Benchmark gegen ein std::stack<int, std::vector<int> > auszuführen und sehen Sie, wie Sie es tun. std :: stack ist ein Containeradapter, und wenn Sie einen Vektor als zugrunde liegenden Container verwenden, sollte er fast so schnell sein wie Ihre selbst erstellte Implementierung.
Der Nachteil ist, dass die std :: stack-Implementierung keine Möglichkeit hat, die Größe vorzugeben. In Situationen, in denen Sie wissen, was die maximale Größe sein muss, wird es ein wenig sein langsamer, da es mehrmals neu zugewiesen werden muss. Danach wird es ähnlich sein.
Wenn Sie die maximale Anzahl an Elementen kennen, die sich zu einem bestimmten Zeitpunkt im Stack befinden, sollten Sie eine std::vector verwenden, für die Sie die Kapazität im Voraus reservieren. Auch wenn Sie die Kapazität nicht kennen, sollten Sie für einen Stack ein std::vector verwenden, das ein paar Mal größer wird (höhere Kosten als ein vorher zugewiesener Vektor beim Wachstum), aber niemals schrumpfen wird. Nach einiger Zeit wird die Speicherzuweisung beendet.
Das Problem mit der Leistung besteht darin, dass std::deque Blöcke nach Bedarf zuweist und sie wieder auflöst, wenn sie nicht mehr benötigt werden (wenn Sie einer Strategie folgen). Wenn Sie std::deque füllen und löschen, werden häufig Zu- und Abmeldungen vorgenommen kontinuierlich.
Tags und Links c++ stack performance deque