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 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 von hanselmansel:

Schuss ins Blaue

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

Und voll daneben geschossen.

[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.