was ist schneller std::list, oder eigene verkette Liste?
-
jepp doppelt verkettet.. mein ich:)
was gibt es da für optimierungen?
-
Wäre eine Frage wie "was ist schneller" nicht was für das FAQ? Oder auch Fragen zur Geschwindigkeit der stl.
Der C++-Standard sagt, wie eine std::list auszusehen hat. Wie die konkrete Implementierung aussieht wird nicht definiert. Die eine Implementierung kann schneller als die andere sein.
Die andere Frage ist, ob das wirklich relevant ist. Ich verwende immer std::list, std::vector, std::irgendetwas, wenn das passt. Es muß schon einen sehr guten Grund geben, es nicht zu verwenden.
In den allermeisten Fällen ist es wichtiger, daß der Code schnell genug ist (und das ist std::list in aller Regel) und lesbar ist. Wenn ich fremden C++-code ansehe und eine std::list sehe, dann weiß ich ohne mir die konkrete Implementierung anzuschauen: ah - der verwendet eine doppelt verkettete Liste mit bestimmten Eigenschaften.
-
genau das ist der grund von standard containern. wenn ich irgendwo eine std::list sehe, dann weiss ich, was das diese aus einem bestimmten grund gewählt wurde. sehe ich eine std::map, weiss ich auch bescheid. deshalb ist es auch so wichtig, immer die korrekten container zu verwenden, auch wenn man der meinung ist, man könne einfach nen std::vector nehmen und die doppelt verkettung selbst implementieren. das ist für fremdleser unverständlich und führt bei weiterentwicklung mit größerer wahrscheinlichkeit zu problemen.
-
Soweit ich weiß mach der C++ standard nicht nur angaben zur funktionsweise sondern auch zur Laufzeitkomplexität.
-
du könntest eine SkipListe implementieren, dann hast du den Vorteil, dass du in Log(n) Zeit suchen kannst, aber das auf Kosten von etwas mehr Verwaltungsspeicher.
-
templäd schrieb:
Soweit ich weiß mach der C++ standard nicht nur angaben zur funktionsweise sondern auch zur Laufzeitkomplexität.
Das Thema hatten wir hier kürzlich. "Laufzeitkomplexität" bedeutet nicht, daß die Liste besonders schnell oder langsam sein muß. Beim iterieren könnte eine Implementierung nach jeder Iteration eine kurze Verschnaufpause einlegen und die Bedingung wäre erfüllt, sofern diese Verschnaufpausen bei jeder Iteration und immer genauso lang auftreten.
-
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
Hängt also alles vom Anwendungsfall ab.
-
hustbaer schrieb:
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Das kommt wohl auch drauf an was du speicherst, nicht?
-
wiso, das sind doch alles template Container, das heißt, man kann genauso gut auch pointer reinsmeißen oder sonstwas, wenn das die sache so beschleunigen sollte.
-
hustbaer schrieb:
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
Hängt also alles vom Anwendungsfall ab.
Warum tut das bei vector weniger weh, als bei list? Das ist eher andersrum. Wenn ich an einen vector ein Element anhänge, dann muß unter umständen der gesamte Vektor umkopiert werden. Das tut weh. Bei list passiert das nicht.
Ansonsten kann ich Krux unterstützen. Wenn Du eine std::list mit Objekten mit einer eigenen Liste mit Zeigern vergleichst, vergleichst Du Äpfel mit Birnen.
-
Aber bei vector kann im optimalen Fall ein Customchip bzw. ein bestimmter CPU-Befehl einen ganzen Speicherblock von A nach B kopieren, ohne das es bedeutend Rechenzeit kostet.
Bei einer verketteten Liste, woe die Elemente nicht sequenziell liegen sondern verteilt, wird das kopieren schwieriger aber auch nicht nötig (ist halt bei list so). Ist meiner Meinung nach heute nicht so relevant.
-
Artchi schrieb:
Aber bei vector kann im optimalen Fall ein Customchip bzw. ein bestimmter CPU-Befehl einen ganzen Speicherblock von A nach B kopieren, ohne das es bedeutend Rechenzeit kostet.
Das gilt aber nur für triviale Objekte ohne speziellen Kopierkonstruktor.
-
OMG es versteht wieder keiner was ich meine.
Ein Container speicher *immer* Kopien. Wenn man natürlich eine list<blah*> macht speichert diese Kopien von Zeigern, das ist doch logisch.Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.
Genau deswegen tut das bei vector<T> weniger weh, weil da nicht für jedes Element einzeln Speicher angefordert wird, sondern immer gleich für etliche Elemente am Stück - je grösser der vector vor dem insert/push_back war desto mehr.
Das eigentliche Kopieren eines Elements dauert verglichen mit dem new/delete Aufruf meist nicht lange - vorausgesetzt die Elemente sind nicht extrem riesig und haben keinen Kopierkonstruktor der diverse "teure" Funktionen aufruft.
-
hustbaer schrieb:
Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.
Genau deswegen tut das bei vector<T> weniger weh, weil da nicht für jedes Element einzeln Speicher angefordert wird, sondern immer gleich für etliche Elemente am Stück - je grösser der vector vor dem insert/push_back war desto mehr.
das ist aber kein problem von std::list, da sie den speicher über den per template übergebenen allocator anfordert. Theoretisch kann dieser den Speicher im Block anfordern und dann häppchenweise an die List übergeben, nur tut das der standard allocator nicht. Man kann sich aber einen eigenen allocator schreiben oder die von boost nutzen, dann gibt es das von dir angesprochene problem nicht.
Übrigens musst du dich nicht wundern dass du missverstanden wirst, da du von anfang an von kopien sprichst
-
Ich wollte bloss sagen dass es keinen Sinn macht eine eigene List Klasse zu programmieren wenn die eigene Klasse keine "intrusive list" ist.
Was der Einwand mit dem Allocator soll weiss ich nicht, denn einen eigenen Allocator zu schreiben ist wohl in den seltensten Fällen angebracht, und die Boost.Pool Varianten sind zwar schneller aber immer noch langsamer als wenn garkeine Allokationen benötigt werden.
Was an meinem ersten Posting so schwer zu verstehen war weiss ich auch nicht, steht eigentlich alles da. Aber egal.
-
du sagtest:
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
...
Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.und ich sagte daraufhin: Nein, es ist nicht zwingend so.
Und zwar, weil durch alleiniges ändern des allocators aus einer list eine intrusive list werden kann(bzw etwas was die selben eigenschaften einer intrusive list hat)
