Doppelt verkettete Liste sortieren

[Mr.P-Funk]

@ DelphiDeveloper
Der Vorschlag mit TList zu arbeiten, erspart sicher viel Zeit, ist aber nicht ganz das was ich wollte.
Trotzdem THX für die Idee.

@ Niko
MergeSort kenne ich noch nicht... leider :(
Werde mir das aber mal ansehen.

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.
Das Array lässt man dann sortieren und "verbiegt" seine Liste neu (Die Daten davon liegen ja noch im Speicher).

Wenn ich das richtig verstanden habe, würdest du alle Infos die in der Kette stehen auch in das DynArray schreiben. Aber dann würde ein Dreickstausch doch sehr lange dauern, wenn das record aus mehr Feldern bestehen würde...
Oder habe ich das jetzt falsch verstanden? :gruebel:


Ich habe mal ein kleines Beispielprogramm erstellt.
Allerdings raten mir viele Leute davon ab, das so zu machen. Es wäre zu unsicher...
Könnt ja mal reinschauen.

Großes THX an alle! :hello:

cya
MR.P-Funk

[negaH]

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen. Man kann dies noch beschleunigen indem man zur ListB ein Array mit Ln2(ListA.Count) Pointern benutzt. In diesem Array wird ein Zeiger auf das jeweils ListB.Count/Ln2(ListA.Count) Element/Node gespeichert. Beim Enfügen einer Neuen Node wird nun dieses Array per QuickFind durchsucht um die Anfangsnode ab der die Liste itertiert werden muß zu finden. Dies beschleunigt ungemein das sortierte Einfügen in deine ListeB.
Das Zusatzarray wird von Anfang an auf ListA.Count Elemente initialisiert und dann deren enthaltene Pointer nur succesive nach dem Einfügen/Umkopieren der Node geupdatet. Bei diesem Update kann man sich weiter beschränken indem man nur die beiden "Rand" Nodes in diesem Array korregiert.

Hm, ich glaube nicht das ich das verständlich rübergebracht habe

Gruß Hagen

[shmia]

Zitat von Mr.P-Funk:

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.

Da hast du nicht genau hingeschaut.
Das Array aus meinem Vorschlag enthält nur Zeiger (Datentyp PSortItem)
Der typisierte Pointer vereinfacht das Programmieren...

[Hansa]

Zitat von negaH:

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen....Hm, ich glaube nicht das ich das verständlich rübergebracht habe Gruß Hagen

Hehe, ich verstehe das auch nicht. 8) Ich vermute mal, er will das sagen, was man machen sollte : die Liste direkt sortiert aufzubauen und basta. Dann entfällt der Rest sowieso. Muß die Liste unbedingt komplett anders umsortiert werden, tja dann eben wirklich unter dem neuen Sortierkriterium neu aufbauen.

[negaH]

@Hansa, stop mal, will er die Liste umsortieren oder will er einen sortierten Index für die Liste aufbauen ohne die Liste physikalsich umzusortieren ?

Ich war der Meinung das er die Liste umsortieren will. Da er eh schon mit Verketteten Nodes/Elementen arbeitet ist es auch kein Problem sehr schnelle Nodes aus einer Liste zu erntfernen und in eine andere Liste sortiert einzufügen. Dies kostest erstmal keinen zusätzlichen Speicher. Allerdings muß er beim Einfügen einer Node in die neue und sortierte Liste im ungünstigen Falle immer diese Node mit allen Nodes in der Zielliste vergleichen. Dies ist sehr ineffizient. Man könnte nun ein komplettes Array[] of PNode aufbauen das so viele Zeiger wie Nodes in der Liste enthält. Dies kostet Speicher, lässt sich aber per QuickSort einfach und schnell sortieren, wäre vergleichbar mit einem externen Index und kostet im Grunde sehr viele Speicherkopieroperation während der Sortierei.

Ein Kompromiss ist nun eine Lösung die beide primären Varianten vereint, sprich Umsortieren in neue List und dabei ein sehr kurzes Indexarray für die Suche der Einsortierposition der Node.

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Somit wäre mein Vorschlag leicht langsammer beim Suchen der richtigen Einfügeposition, allerdings wird dies durch die wesentlich erhöhten Speicheroperationen bei den anderen Methoden weitestgehend kompensiert. Denn Speicherkopierungen sind wesentlich langsammer auf modernen CPU's also nur readonly durch eine verkettete Liste durchzuiterieren.

Falls das Sortieren der Liste wirklich enorm schnell gehen muß dann kann man das durch eine Erweiterung der Nodes erreichen. Die Nodes selber sind als verkettete Liste linear untereinander verknüpft. Aber gleichzeitig sind sie auch als Binärer Baum, zb. ein AVL oder Red Black Tree aufgebaut. Die Nodes müssten dann nicht mehr doppelverlinkt werden, aber zusätlich benötigen sie mindesten zwei weitere Zeiger -> Left,Right.
Beschränkt sich das Sortieren aber nur auf das Einfügen in einen solchen Tree dann kann man die Left,Right Zeiger später als Prev,Next Pointer für die verlinkte Liste benutzen. Während des Aufbauens des Baumes entsteht also ein ausbalancierter binärer Baum (RB, AVL). Nachdem man alle Nodes so eingefügt hat, kann man mit einer Rekursiven Funktion die den Baum sequetiell alphabethisch abarbeitet, neu zu einer normalen doppeltverlinkten Liste ummodscheln Klar, einmal in eine Liste umgemodschelt kann man keine neuen Nodes mehr sortiert als Baum einfügen.
D.h. temporär beim Umsortieren werden die Nodes statt in einer linearen Liste in einen binären Baum eingearbeitet, aus den Prev,Next Zeigern werden die Left,Right Zeiger für den AVL/RB Tree. Nachdem man alle Nodes so binär umkopiert hat wird der Baum neu verlinkt so das eine Liste entsteht.

Dieses Verfahren ist Ln2(List.Count) schnell, asymptotisch schneller als QuickSort !! benötigt keinen zusätzlichen Speicher und keine Kopieroperationen ausser dem Umbiegen der Zeiger. Allerdings ist es komplex und nicht einfach zu coden.

Gruß Hagen

[Mr.P-Funk]

@ Shima
Upps zu schnell gelesen...
Aber die einen typisierten Zeiger zu nehmen ist gut, warum bin ich da nicht selber drauf gekommen ...
Damit ist der Aufwand wohl echt geringer.

@ negaH
Das hört sich ja interessant an, aber ich hatte schon Probs das überhaupt zu verstehen, nen Code kann ich mir nur schwer vorstellen...
Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??

Ich erkläre den Thread als geschlossen; meine Fragen wurden beantwortet
THX @ all

[negaH]

Zitat:

Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??

Ja, ich habe irgendwie schon alles mal programmiert AVL und RB Trees und verlinkte Listen auf jeden Fall, allerdings noch nie eine solche Kombination wie ich sie oben beschrieben habe. Gehen tut das auf alle Fälle, davon bin ich überzeugt, und die Abschätzung der Komplexität eines solchen Mischalgos. kann man auch trocken auf rein theoretischer Basis machen.

Hier im Forum, meine ich mich erinnern zu können, muß es auch ein Source von mir für einen AVL Tree geben. Kann mich halt nicht erinnern im welchen Zusammenhang, eventuell war das der Thread mit dem DoubleChecker/Doppelte Dateienfinder oder sä.

Zum Verständnis nochmal:

Du hast eine doppelt verlinkte Liste. Jedes Element dieser Liste nenne ich mal Node. Eine Node hat zwei Felder/Member mit Namen Prev: PNode und Next: PNode. Über diese beiden Zeiger wird das Element mit seinem Vorgänger und Nachfolger verlinkt. Die doppelte Verlinkung macht es möglich diese Node sehr schnell aus der Liste zu entfernen, oder die List vorwärts und rückwärts zu iterieren.

Ein binärer Baum hat auch Elemente, nenn sie mal Node. Jede Node in einem binären Baum hat auch zwei Zeiger vom Typ PNode, allerdings benennt man sie meisten Right und Left. Zusätzlich enthält sie noch die Daten. Das die Node nur zwei untergeordnete Nodes enthalten kann kann nur ein binärer Baum entstehen. Die Art und Weise wie nun der Baum ausbalanciert wird, sprich ob die Anzahl der untergeordneten Node in Right und Left immer nur um +-1 differieren kann bestimmt den Typ des Baumes. Können sich diese Anzahlen stark unterscheiden dann ist der Baum nicht ausbalanciert, er wäre ein stinknormaler binärer Baum. Solche Bäume haben keinen Suchvorteil, d.h. deren Komplexität ist im schlechtesten Falle genauso schlecht wie eine lineare Liste. Ist die Anzahl der Linke und Rechten Hälten der Node aber immer fast identisch dann ist der Baum ausbalanciert. Die Art und Weise wie man nun effizient erreicht WIE dieses ausbalancieren funktioniert bestimmt den "Namen" des Trees. Die meistbekannten Vertreter sind die AVL und Red Black Trees. (frag mich jetzt nicht was AVL genau bedeutet, müsste ich erst nachschlagen). Gut, beide Trees balancieren ihre Nodes direkt beim Einfügen und auch Löschen einer Node in den Baum aus.

So, nun muß man noch eine Frage beantworten: Gibt es in deiner Liste Duplikate ? Das ist wichtig da es in einem normalen binären Baum niemals direkt die Möglichkeit gibt Duplikate zu speichern. In jedem Falle müsste man entweder zu einer Node eine weitere verlinkte Liste einführen in die dann alle Duplikate verwaltet werden, oder aber die Ausbalancierung würde nicht mehr korrekt funktionieren.

Ich gehe mal von Listen ohne Duplikate aus. Was passiert nun beim Umsortieren ?
Man entfernt die erste Node aus der Liste und fügt sie in die Rootnode des Tree sortiert ein. Dabei wird sie vorerst einfach Left in Root. Nun nimmt man die zweite Node aus der Liste und macht sie zu Right der Root. Anschliesend vergleicht man Left mit Right und eventuell müssen sie die Plätze tauschen, weil Left größer Right ist. Das geht nun so lange weiter bis die Liste leer ist. Auf der anderen Seite entsteht ein binärer Baum der ansich sortiert ist. Ganz ganz unten Links in diesem Baum steht die Node mit dem kleinsten Wert, ganz unten Rechts diemit dem größten Wertund gleich unterhalb der Root stehen die zwei Nodes die exakt in der Mitte aller Wertigkeiten stehen. Man kann nun sehr leicht rekursiv diesen Baum von Links nach Rechts auflösen und alle Nodes wie eine normale Liste doppelt verlinken. Schwups wurde die Liste mit der bestmöglichen Komplexität und geringstmöglichen Overhead und fast 0 Bytes zusätzlichen Speicher umsortiert.

Auf Grund der direkten binären Suche im Baum benötigt man bei zb. 1024 Nodes maximal 10 Vergleiche um deren Einfügeposition zu finden. Pro Node fällt immer nur das Umsetzen der Zeiger als Speicheroperation an, es müssen also keine großen Speicherbereich umkopiert werden. Die Neuverlinkung hat nur lineare Komplexität.

Gruß Hagen

[Hansa]

Bin mir fast sicher, daß es das hier ist. Aber wie gesagt : so was ist nicht gerade trivial.

http://www.delphipraxis.net/internal...t=doublekiller

[mleyen]

Zitat von negaH:

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Ich weiß der Thread ist schon uralt, aber für mich gerade aktuell da ich auch eine eigene spezielle Liste bastle.
Ziemlich interessant wie du den Ramverbrauch der CPUlast gegenüberstellst. (Ich war immer der Meinung, dass das bei Such/Sortierverfahren, aufgrund des dynamischen Inhalts, nahezu nicht geht)
Aber was tut bitte "Ln2()"?

[Sherlock]

Ins blaue geraten ist das der Logarithmus mit Basis 2.

Sherlock