Elemente suchen: std:list vs. std:vector
-
Habe bischen bei google gestöbert, und folgende seite gefunden, in der steht, das Suchen von elemente bei listen "sehr langsam" und bei vectoren "schnell" ist.
http://www.cpp-tutor.de/cpp/le18/le18_01.htm
Aber da das suchen von Elementen eine travestierung der Elemente bis zum "gefunden" element erfordert, dürfte ja das performance technisch keine großen aufwand sein oder? Das direkter zugriff auf eine Element per index bei liste lang dauer im gegensatz zu vector ist mir klar aber suchen!??
Oder ist das springen Pointer zu Pointer bei ner liste so rechenintensiv?
-
Es ist mit Sicherheit beides sehr schnell. Verglichen mit einer Suche in einem vector ist die Suche bei list jedoch ein wenig komplexer. Sollte aber nicht so sehr ins Gewicht fallen...
-
Antwort schrieb:
Es ist mit Sicherheit beides sehr schnell.
Du meintest sicher *langsam*, oder?
Abgesehen davon ist das Suchen in Liste und (unsortiertem) Vektor quasi gleichschnell, nämlich linear abhängig von der Größe (also Θ(n)).
-
Noch was, Boris: Du hast Dich nämlich verlesen. Es steht dort sowohl bei Liste als auch bei Vektor, dass das Suchen *langsam* ist, und nicht schnell (bei der Liste steht da zwar "sehr langsam", was aber auch nur bedingt bzw. überhaupt nicht stimmt).
-
Noch ein Zusatz: Auf der Seite tummeln sich noch andere Fehler. Das ist also mit Vorsicht zu genießen.
-
Konrad Rudolph schrieb:
Abgesehen davon ist das Suchen in Liste und (unsortiertem) Vektor quasi gleichschnell, nämlich linear abhängig von der Größe (also Θ(n)).
Beide haben die gleiche Komplexität (und spielen deshalb in der selben Liga), dass heißt aber natürlich nicht, dass beide gleich schnell sind. Für gewöhnlich (d.h. auf einem modernen Rechner) ist die Suche in einem zusammenhängenden Speicherbereich (Vektor) deutlich schneller als die Suche in einer verketteten Liste. Stichwort: Lokälität und Cache-Effizienz.
Unabhängig davon, sollte man mit absoluten Begriffen wie "langsam" oder "schnell" vorsichtig sein. Ob etwas zu langsam oder schnell genug ist, hängt schließlich von der konkreten Situation ab. Besser man bleibt bei der Komplexität, so hat man zumindest eine grobe Richtlinie.
-
Bei beiden ist die Suche O(N). Bei Listen wird allerdings der Cache nicht gut genutzt, und man muss sich von Element zu Element weiterhandeln, womit die CPU auch schlechter (langsamer) klar kommt als mit nem einfachen Array.
-
hustbaer schrieb:
Bei beiden ist die Suche O(N). Bei Listen wird allerdings der Cache nicht gut genutzt, und man muss sich von Element zu Element weiterhandeln, womit die CPU auch schlechter (langsamer) klar kommt als mit nem einfachen Array.
Gut, Caching hatte ich bei meiner Darstellung nicht beachtet. Aber das Entlanghangeln an den Elementen einer Liste ist nicht wesentlich langsamer als der Zugriff auf Array-Elemente (ich würde jetzt mal grob schätzen zweimal so langsam), daher meine Aussage, die beiden seien gleichschnell. Die Speicher-Lokalität macht diese Aussage natürlich ein wenig zunichte.
-
n vector ist nur dann viel schneller, wenn er sortiert ist und man entsprechend sucht.
-
Naja... bei einer verketteten Liste muss erstmal eine Node fertig in den Cache (und von dort weiter in die ALU) geladen sein (zumindest der "next" Zeiger der Node) damit die CPU die nächste Adresse die geladen werden muss kennt. Denke schon dass das das Pipelining etwas ausbremst...
Müsste mal nen Benchmark machen, würde mich interessieren ob das wirklich "nur" 2x langsamer ist.Wenn die Liste "am Stück" befüllt wird müsste es noch halb so wild sein, da ein guter Allocator auch etwas auf "locality" achtet -- wenn die Liste allerdings im Laufe des Programmes "mal hier eins mal da eins" befüllt wird stehen die Chancen nicht schlecht dass jede Node in einer anderen Cache-Line liegt.
Spielt natürlich nur dann eine Rolle wenn die Liste entweder sehr sehr lange ist, oder dauernd von irgendwas aus dem Cache getreten wird.
Verkettete Listen sind schnell, aber nicht so schnell wie Vektoren
-
hustbaer schrieb:
Müsste mal nen Benchmark machen, würde mich interessieren ob das wirklich "nur" 2x langsamer ist.
Wie gesagt, diese Schätzung ignoriert die Caching-Problematik.
-
Konrad Rudolph schrieb:
hustbaer schrieb:
Müsste mal nen Benchmark machen, würde mich interessieren ob das wirklich "nur" 2x langsamer ist.
Wie gesagt, diese Schätzung ignoriert die Caching-Problematik.
Wie groß der Unterschied Vektor vs. List ist hängt natürlich von der konkreten Situation ab (Anzahl der Elemente im Container, Häufigkeit der Suche, Verhältnis gefunden/nicht-gefunden und Kontext in dem der Code aufgerufen wird).
Für ganz einfache Experimente komme ich bei mir auf ca. 3x langsamer. Als jemand der schon einige SAT und ASP-Solver implementiert hat, weiß ich aber, dass auch deutlich größere Unterschiede auftreten können. Aber wie immer: YMMV und im Zweifelsfall lieber messen als raten.
