verkettete Liste

[helga5]

Ich habe eine Frage bezüglich der Schnelligkeit einer verketteten Liste.
Es gibt 2 Methoden:
- Mit Zeigern
- dynamischen Array
(die Dimensionierung kann man in der Laufzeit mit setlength(X,4) erweitern)

Nun zu meiner Frage.
Was ist schneller? Mit Zeigern oder dynamischen Array?

[mkinzler]

Wie meinst du schneller? Beim Anlegen, einfügen, Sortieren?

[helga5]

Eigentlich nur beim Anlegen und Einfügen. Denn sortieren braucht man beim hashtables nicht.

Im Buch "Grundlagen und Profiwissen" von Walter Doberenz und Thomas Kowalski ist auf Seite 698 ein Diagramm mit verschiedenen Sortiermoeglichkeiten (Austausch, Auswahl, Bubblesort und Shellsort) bezüglich Schnelligkeit getestet in ms.
Shellsort ist am schnellsten.

Ich dachte evt. hat sich schon jemand zu meiner Frage die Mühe gemacht dies zu testen. Aber sicherlich ist auch ganz interessant zu erfahren, wenn man sortieren will. Dies beabsichtige ich aber nicht zu tun.

Und danke für die Antwort.
helga

[mkinzler]

Ich würde schätzen, das dynamische Array in der Anlage und beim Einfügen etwas schneller sind. Beim Sortieren aber nicht.

[DGL-luke]

beim einfügen? würd ich nicht sagen, immerhin muss man alles hinter dem eingefügten verschieben, während man bei der verketteten liste nur die zeiger ändern muss.

[mkinzler]

M.E. muß bei der verketten Liste das Element ja auch erzeugt werden. Soll sortiert werden, ist die verkette Liste aber auf jeden fall besser.
Es ist sowieso fraglich ob ein Geschwindigkeitsvorteil einer variante überhaupt merklich ist.

[hanselmansel]

Schuss ins Blaue

Wird ein dynamisches Array nicht intern selbst über verkettete Listen realisiert?

MfG

hanselmansel

[alzaimar]

Hier hilft wieder ein Exkurs in Komplexitätsberechnung: Sei LL die (doppelt) verkettete Liste (Linked List) und DA das dynamische Array;
Anhängen:
LL = O(1)
VA = O(1)
(VA einige Takte schneller, da nur ein Speicherzugriff, LL muss noch die Zeiger aktualisieren)

Sortiert Einfügen:
LL = O(n)
VA = O(n) (O (n log n) für binary search und O(n) für das 'Platz machen', also Verschieben)
(tendentiell VA schneller, da das verschieben des Arrays zum 'Platzmachen' sehr schnell geht)

Löschen:
LL = O(n)
VA = O(n)
(tendentiell VA schneller, da das verschieben des Arrays zum 'Platzmachen' sehr schnell geht)

Sortieren:
Beide gleich, optimal ist O(n log n)

Wenn man das dynamische Array jeweils in seiner Größe verdoppelt, kann man diesen Zeitaufwand vernachlässigen.

Was bedeutet das?
O(1) = Die Operation ist immer gleich schnell, unabhängig von der Anzahl der Elemente.
O(n) = Zeitaufwand steigt linear: Verdoppelung der Listengröße => Verdoppelung des Zeitaufwandes
O(n log n) [log hier log2] = Zeitaufwand steigt logarithmisch. Verdoppelung der Listengröße => ca. 10% höherer Zeitaufwand.
...

Zitat:

Zitat von helga5

Im Buch "Grundlagen und Profiwissen" von Walter Doberenz und Thomas Kowalski ....Shellsort ist am schnellsten.

Quicksort wurde nicht getestet? Merkwürdig.

Unterm Strich verwende ich verkettete Listen nicht mehr (die haben keinerlei Vorteile). Für einfache Listen verwende ich ein dynamisches Array oder eine T(String)List, wenn mir die Performance nicht so wichtig ist. Ansonsten eine Hashmap oder gleich eine gute DB.

Wer Listen mag, sollte aber eine Skiplist verwenden, die sind einfach sauschnell, praktisch und nur minimal langsamer als eine (gute) Hashmap. Leider ist der Speicherbedarf pro Element ziemlich hoch (ca. 32 Byte für Hilfszeiger).

Zitat:

Zitat von hanselmansel

Schuss ins Blaue

Wird ein dynamisches Array nicht intern selbst über verkettete Listen realisiert?

Und voll daneben geschossen. :zwinker:

[helga5]

Ich habe mir die Komplexitätsberechnung angesehen. Demzufolge schneidet in allen Punkten der DA (VA war wohl ein Schreibfehler) am besten ab, wenn man Deiner Ausführung glauben schenken möchte. Ich gehe mal davon aus, dass eine einfach verkette Liste langsamer ist als eine doppelt verkettete Liste?
Dann frage ich mich nur noch, wozu man die LL noch braucht?

Mit dem Qicksort habe ich im Internet folgende Seite gefunden.
Da werden alle Sortiermöglichkeiten vorgestellt.
http://www.gymmelk.ac.at/nus/Delphi/Delphi11.htm
Soll etwas schneller als shellsort sein, da rekursiv.
Soll das heissen, dass rekursiv schneller als iterativ ist?

Noch eine kleine Randbemerkung:
Mit den dynamischen arrays arbeite ich sowieso viel lieber, es ist einfach viel bequemer. Beim Einfügen musste man immer rumfummeln und dann noch beim Auslesen eine Hilfsvariable hernehmen, hat mich schon immer irgendwie genervt. Ich habe damit viel zu viel Zeit verschwendet das ganze inhaltlich zu verstehen. Ich denke nur an den B-Baum.

Danke für die Erklärung
helga

[mkinzler]

Zitat:

Ich gehe mal davon aus, dass eine einfach verkette Liste langsamer ist als eine doppelt verkettete Liste?

Das Einfügen usw. geht sogar langsamer, da ja doppelt verkettet wird. Bei doppelt verkette Listen kann man in beide Richtuhen navigieren, wähhrend man bei der einfachen zu jedem element nur den Nächsten ermitteln und somit nicht rückwärts navigieren kann.

[alzaimar]

Zitat:

Zitat von helga5

Soll etwas schneller als shellsort sein, da rekursiv.
Soll das heissen, dass rekursiv schneller als iterativ ist?

Nein. Es kommt hier auf das Verfahren an. Quicksort ist zwar von der Komplexität her genauso wie Shellsort (und auch Mergesort), in der Praxis hat sich aber quicksort bewährt, weil es einfach am kompaktesten ist, also pro Vergleich, Vertauschen etc. am wenigsten Overhead produziert.

Eine iterative Variante von Quicksort, die den rekursiven Aufruf mit einem eigenen Stack simuliert, ist noch marginal schneller (ca. 4%).

Wirklich schnell ist nur die Skip list, die sowohl der LL, als auch dem DA (wie komm ich nur auf VA?) in allen Belangen haushoch überlegen ist.

[Lemmy1]

Hrm also das anhängen eines Elementes an ein dynamisches Array ist nicht zwingend O(1), da Windows u.U. einen neuen Speicherbereich finden muss, da Arrays nicht fragmentieren können.

Ergo ist das anhängen eines Element O(n) (n=Anzahl Element im Array).

[alzaimar]

Ich schrieb[*], das man die Größe des dynamischen Arrays verdoppelt, wenn das neue Elemnt nicht mehr hineinpasst. Windows vergrößert von sich aus gar nichts, oder?
Aber wenn ich das mache, und zwar immer verdoppeln, kann man das vernachlässigen, auch rechnerisch, ergo O(1).

[edit] (*) Nee, hab ich gar nicht geschrieben, sondern nur gedacht, das ich das geschrieben habe :wall: . Aber wer nach vor jedem Append das Array erstmal vergrößert, ist selbst schuld. [/edit].

[Lemmy1]

Yup beim Verdoppeln hast recht. Aber das geht ja nur, wenn ich zum Beispiel Zeilen aus einer Datei auslesen ohne die Gesamtgröße zu kennen.

Wenn ich aber sowieso nur ein einziges Element anhängen will, dann bringt mir Verdoppeln halt oft nix

[alzaimar]

Zitat:

Zitat von Lemmy1

Wenn ich aber sowieso nur ein einziges Element anhängen will, dann bringt mir Verdoppeln halt oft nix

Dann ist aber auch eine Komplexitätsbetrachtung für'n A****, oder? Egal., Ich hätte es dazu schreiben sollen und Dein Einwand ist berechtigt.

[himitsu]

Also wenn ich mir meinen MM so anseh, dann kommt's da auf die Größe das Array's an.

bei 'nem großen Array und vielen einzufügenden/anzuhängenden Einträgen ist auf jedenfall die verkettete Liste schneller, da die kleinen Speicherblöcke schneller/optimaler verwaltet werden.
Es sei den du verwendest 'ne optimierte SetLength-Funktion (hab z.B. sowas für Strings, da kann man das Verhalten bei Längenändernung beeinflussen), da könnte es sich dann eventuell wieder etwas ausgleichen.


Ach ja, was das Verdoppeln angeht ... sowas würde ich wohl eher nicht anraten ...stellt euch doch nur mal vor das array ist schon echt groß und ratet mal, wie extrem groß es dan werden würde :zwinker:

http://www.delphipraxis.net/internal...=451739#451739 in dem Beitrag sieht man mal mein SetLength (Parameter und so) und da kann man dann halt angeben wie und in welchen Schritten der String (ist ja auch nur ein dynamisches CharArray) vergrößert/verkleinert wird.

[alzaimar]

Wie immer, muß man zwischen Theorie (Komplexitätsbetrachtung) und Realität unterscheiden.

Wie ich schon sagte, bei einem dynamischen Array muß man die Größe jeweils verdoppeln (oder jedenfalls um einen Faktor vergrößern), und nicht um einen konstanten Wert. Ein konstanter Wert wird die Komplexität von O(1) auf O(n) verschlechtern, eine Vergrößerung um einen Faktor ('2') eben nur marginal. Warum? Weil dieser Umstand bis im Zahlenraum von Integern nur maximal 31 mal vorkommen kann. Bei 2 Milliarden Werten ist der Aufwand dann zu verschmerzen und geht auch rein rechnerisch gegen 0.

Bei einer echten Anwendung, wie himitus MM (Memory-Manager?) wird gesucht, gelöscht, einfügt etc. Wer da die Nase vorn hat, hängt wirklich davon ab, was am häufigsten ausgeführt wird. Ich kann mir nicht vorstellen, das ein dynamisches Array, das anfangs auf ein paar 100k dimensioniert ist, performancetechnisch von einer LL abgehängt wird. Aber erst der Versuch macht schlau, und bis dahin vertraue ich himitsus Erfahrung.

Ich kann mir aber nun wirklich nicht vorstellen, das eine verkettete Liste in einer App gegenüber einer Skiplist oder Hashmap wirklich die Nase vorn hat. Na ja, vielleicht bei < 20 Elementen...

[Khabarakh]

Borland verwendet für seine TList-Implementation (bei mehr als 64 Einträgen) eine Vergrößerung von 25%, damit sollte der ungenutzte Speicher wirklich nicht sehr ins Gewicht fallen.
Aber eigentlich dachte ich, dass sich in der Praxis etwa der Faktor 1,7 bewährt hätte :gruebel: .

[add]
Microsoft hält sich im .Net-Framework eher daran: 200% der alten Capacity.
Wer beide Werte nicht mag, kann sich ja immer noch eine eigene Klasse anlegen ;) .
[/add]

[himitsu]

eine prozentuale Änderung macht sich eh mehr schlecht, als recht.
wenn die Liste klein ist, dann ist die änderung winzig und bei 'ner großen Liste ist die änderung rießig ... besser ist halt ein Wert, der sich nach der Elementgröße und der vermutlichen Menge neuer Elemente, oder halt wie oft/schnell was Neues eingefügt wird richtet.

[alzaimar]

Zitat:

Zitat von himitsu

eine prozentuale Änderung macht sich eh mehr schlecht, als recht.
wenn die Liste klein ist, dann ist die änderung winzig und bei 'ner großen Liste ist die änderung rießig ... besser ist halt ein Wert, der sich nach der Elementgröße und der vermutlichen Menge neuer Elemente richtet.

Nein, stimmt nicht. Also, der erste Satz stimmt nicht. Der Zweite schon, aber woher willst Du denn wissen, wieviel vermutlich dazukommt? Wenn Du das wüsstest, könntest Du die Liste gleich groß genug machen.

Eine Liste, die ihre Größe jeweils verdoppelt, tut dies (bei einer angenommenen Anfangsgroße von 1000 Elementen) nur 21x in ihrem Leben. Und das auch nur, wenn man sie mit 2Mrd. Elementen zuballert, aber wer macht das schon? Im richtigen Leben dürfte sie sich maximal 10x vergrößen. Dann fasst sie immer noch 2^20 Elemente, und das sollte doch reichen. Die Wartzezeit, um eine Liste von 5 auf 10MB zu vergrößern, liegt bei wieviel? 10ms? Und selbst wenn das viel viel langsamer wäre, würde das nur 1x vorkommen. Da ist mir das doch schnurz.

Eine prozenturale Änderung spiegelt genau das wieder, was gerade mit der Liste passiert. Wenn ich als Programmierer das DA anfangs auf 10 Elemente beschränke, erwarte ich i.A. keine 500.000.000 Elemente in der Liste, sondern eher weniger. Wenn ich nun ein 11.Element einfüge reagiert die Liste ziemlich schlau: Sie macht Platz für weitere 10 Elemente. Das ist nett. Und wenn ich dann 100.000 Elemente drin habe, und will das 100.001te einfügen, 'geht die Liste davon aus', das ich gleich noch ein paar hinterher schmeisse. Ergo vergrößert sie sich gleich auf 200.000.

Eine Vergrößerung um immer -sagen wir- konstant 10 oder 1000 Elementen ist dagegen ein echter Hemmschuh. Natürlich wird der Speicher so nicht unnötig verbraten, aber das ist mir völlig schnurz. Wichtiger ist hier doch die Performance, oder?

Ich hatte mich mal ne Weile mit dieser 'Technik' beschäftigt... Man merkt performancetechnisch einfach nicht, das sich da eine dynamische Liste von der Größe her verdoppelt: Ob ich die Liste gleich 10000000 Elemente groß mache, oder dynamisch vergrößere (x2), ist wirklich kaum ein Unterschied. Wenn ich die Liste dagegen jeweils um 1000 Elemente vergrößere schon. Das ist doch logisch.

Beispiel: Eine Liste umfasst anfänglich 1000 Elemente. Nun fülle ich die Liste mit 100000 Elementen. Immer, wenn ein Element nicht mehr reinpasst, vergrößere ich sie, und zwar:
a) um jeweils 1000 Elemente oder
b) ich verdopple die Listengröße.

Bei a) habe ich insgesammt 4950000 Elemente bewegt, bei b) dagegen nur 130048.

Imho macht sich a) mehr schlecht als recht .... :zwinker:

[himitsu]

Ich hab ja nicht gesagt, daß es einfach ist, aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

[alzaimar]

Zitat:

Zitat von himitsu

..., aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

Das lass ich nicht gelten. Welcher Wert ist 'passender'? Welche Heuristik zur Ermittlung der Größenänderung ist besser als die Verdopplung? Ohne konkretes Beispiel bleibt die Vergrößerung per Faktor (egal welcher) die bessere Variante, als die Vergrößerung um einen konstanten Wert.

Ich kann ja auch einfach sagen: Der optimale Vergrößerungsfaktor ist der, der sofort (per TGlasskugel) die optimale Größe einstellt. :mrgreen:

[DGL-luke]

Dafür wäre wohl ein

Delphi-Quellcode:

procedure TMyList.BeginUpdate(Capacity: Cardinal);

bzw.

Delphi-Quellcode:

property Capacity: read FCapacity write SetCapacity;

angebracht...

[Elvis]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von himitsu

..., aber wenn man statt der 1000, um die jedesmal vergrößert wird, ein passenderer Wert nehmen würde, dann wäre halt das andere wieder besser.

Das lass ich nicht gelten. Welcher Wert ist 'passender'? Welche Heuristik zur Ermittlung der Größenänderung ist besser als die Verdopplung? Ohne konkretes Beispiel bleibt die Vergrößerung per Faktor (egal welcher) die bessere Variante, als die Vergrößerung um einen konstanten Wert.

Ich habe mich hier auf 172% eingeschossen. Ist IMO ein optimaler SWA (StiNo-Wachstumsfaktor-Arraybasierter-Container :mrgreen: ).
Wenn es wirklich darum geht noch ein Quentchen rauszuquetschen[1] feile ich aber auch an der Größe.
Oft ist es besser einen Container, der theor. größer werden kann, nicht bei 0 oder 10 Elementen zu initialieren. Eine Zahl, die bei möglichst vielen kleinbleibenden Instanzen eine Kopiererei verhindert finde ich da viel netter. So spielen nur die großen Ausreißer Xerox. :mrgreen:


[1]welches dank X-Wiederholungen schon in merkbare Zehntelsekunden ausarten kann, die zusammen mit 5 anderen Methoden zu einem ekligen Lag führen könnten, das ...

Lange Rede, ganz wenig Sinn: Probiere mal 172% statt 200%. ;)

[alzaimar]

Zitat:

Zitat von Elvis

Lange Rede, ganz wenig Sinn: Probiere mal 172% statt 200%. ;)

Unter welchen Bedingungen hast Du das denn rausgefunden?

Ich hab mal eine Reihe von 'optimalen' Faktoren für das Wachsen von Hashtabellen gefunden (das müssen ja Primzahlen sein). Da hat sich doch tatsächlich Einer die Mühe gemacht, die 32 Primzahlen bis 2^31 aufzulisten, die seiner Meinung nach eine optimale Größe ergeben. Leider hat er nicht bedacht, das er nur eine (irgendeine) Testumgebung hat, die sich nicht mit z.B. Meiner deckt. Na ja, das hätten ja durchaus magische Zahlen sein können. Es war aber nur Quark.

Deshalb kann es sein, das die 172 (Andere sprechen von 166) Prozent besser sind, aber in meiner Umgebung bisher nicht. Es macht einfach keinen Unterschied, ob ich nun verdopple, oder ver 1,72fache. Wie gesagt. in meinem Fall.

Übrigens gibt es auch Ansätze, die Fibionacci-Zahlenreihe zu verwenden.

Mir ging es aber ursprünglich sowieso nur darum, zu zeigen, das eine Vergrößerung um irgendeinen Faktor in der Komplexitätsbetrachtung gegenüber einer konstanten Erhöhung vernachlässigbar ist. Ob das 166, 172, 172.163 oder 200 sind, ist dabei unerheblich.

[himitsu]

Na ja, im MM nehm ich ja och 130%/70%, aber bei den String hab ich's infach so gelöst, dat die Größe auf die nächte Volle aufgerundet wird, dat macht vorallem viel aus, wenn sehr viele kleine Änderungen gemacht werden (z.B. per StringReplace und Co.)

TGlasauge ist gut, weiß nur nicht mehr wo ich dat abgespeichert hatte ... aber hier wurde ja eh schon zuoft festgestelt, daß man eigentlich nur "optimal" optimieren kann, wenn man genau weiß, was auf einen zukommt ... ansonsten kann man nur versuchen auf irgendeine Weise das ganze etwas optimaler zu machen (für einen kleinen Bereich der möglichen Änderungen).