Schnelles suchen in einfach verketeter Liste

[theo]

Nö, weil die Reihenfolge der Objekte im Speicher bei verketteten Listen überhaupt nicht der eigentlichen Listen-Reihenfolge entsprechen muss.
Wenn du z.B. in der Mitte deiner Liste ein Objekt einfügst, dann kommt das wohl irgendwo in einen hinteren Speicherbereich nach dem letzten Element, bzw. man kann gar nicht sagen wo es hinkommt. Wichtig ist ja nur, dass das vorherige Element weiss, wo die Reise hingeht.

[pluto]

Also das ist der unterschied ! Stimmt hatte ich ganz vergessen.

Also muss ich in meiner Liste immer suchen. Wenn es eine Verkettet liste gibt. Ich kann höchstes den Suchbereich Eindämmen, richtig ?

Wie oben beschrieben z.b. oder gibt es noch mehr Möglichkeiten ?

[theo]

Also das ist der unterschied ! Stimmt hatte ich ganz vergessen.

Also muss ich in meiner Liste immer suchen. Wenn es eine Verkettet liste gibt. Ich kann höchstes den Suchbereich Eindämmen, richtig ?

Wie oben beschrieben z.b. oder gibt es noch mehr Möglichkeiten ?

Liest du hier: http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29" onclick="window.open(this.href);return false;
z.B. Adaptive Listen

Aber nimm doch ne TList, das ist echt viel praktischer. Verkettete Listen braucht man doch eher in Sonderfällen.

[pluto]

TList ist nicht praktisch für meine zwecke Stichpunkte:
Insert und Deletet.

Das ist der Punkt warum ich keine Array leiden kann.
Danke Für den Link !

[theo]

TList ist nicht praktisch für meine zwecke Stichpunkte:
Insert und Deletet.

Naja, es kommt halt auf die Performance unter dem Strich an.
Bei den meisten Anwendungen würde ich eher etwas mehr Zeit für Einfügen etc. opfern als für's Suchen. Aber ich weiss ja nicht, was du letztendlich machen willst.
Am Besten du misst mal die Zeit und den Speicherverbrauch für beide Varianten mit der gleichen Anzahl Elementen. Einfügen und Suchen.
Das Resultat würde mich auch interessieren.
Dann siehst du auch, ab wievielen Elementen der Unterschied praktisch überhaupt relevant wird und ob sich der "Stress" mit der verketteten Liste anstatt TList für deine Zwecke überhaupt lohnt.
Ich tippe mal auf "nein".

[theo]

@Pluto: Habe hier noch eine Information gefunden:
http://www.riversoftavg.com/efficiencyt ... nglist.htm" onclick="window.open(this.href);return false;

Leider auf Englisch.
Er sagt in etwa, dass die Knoten für eine verkettete Liste zu erstellen langsamer sei als das einfügen in TList und dass man die verkettete Liste gleich vergessen kann. Auch das traversieren mit TList sei schneller.

Das erste kommt wahrscheinlich daher, dass TList im voraus einen gewissen zusammenhängenden Speicherbereich alloziert, während du mit verketteten Listen für jeden Knoten Speicher reservieren musst, was langsamer ist.
Ich hab selber auch schon verschiedene Tests gemacht und bin immer wieder auf die gute alte TList zurückgekommen.

[theo]

Noch was für Christian, dann haben wir das Thema dann langsam durch
TStringList macht einen binary search wenn sie sortiert ist. (Siehe TStringList.Find in stringl.inc).
Du könntest also deinen Suchstring inklusive TObject via AddObject in die Stringlist schreiben. Das wäre dann ziemlich einfach

[pluto]

und ob sich der "Stress" mit der verketteten Liste

Also ein Aufwand ist das nicht mehr für mich, ich habe für mich einmal eine nette kleine Klasse geschrieben TMyObjectList, die bedingung ist so wie bei der "richtigen" TObjectlist.

Code: Alles auswählen

dass TList im voraus einen gewissen zusammenhängenden Speicherbereich alloziert

Das habe ich auch schon in mehren Thread gelesen. Das es langsamer sei, speicher nach und nach zu allozieren.... Die Frage ist wie kann ich das Optimieren.

Das TList schneller sein soll beim Hinzufügen/löschen/Updaten kann ich mir nicht vorstellen:
Wenn ich Hinzufügen oder Löschen möchte muss ich doch immer eine schleife starten vom Index der hinzugefügt oder gelöscht werden soll. um dann die Elemente nach und nach um ein Element zu verschieben. Das habe ich oft genug gemacht. Das TList auf ein Array basiert, gehe ich davon aus das die das genau so machen müssen.

Kann sein das sich TList für kleine Listen gut eignen würde. Wobei Klein auf jeden Rechner anders definiert sein dürfte.

Der Vorteile von einem Array(TList) ist halt das man direkt drauf zugreifen kann.

Ich kann mir nicht vorstellen das TList mit 20.000 Elemente umgehen kann. d.h.: Einfügen von 10 Elemente ab Position X Löschen von 30 Elementen von Position X.

Gut, Tlist oder TObject list(ich weiß irgendwie nie den Unterschied) ist vom Aufbau her einfach so das man damit gut umgehen kann und arbeiten kann. Meine eigene Klasse die ja eine Doppelt Verkette Liste nutzt ist genau so einfach.

Mal ein Anders beispiel:

Ich möchte mir ja meine eigene Editor Komponente schreiben.
Sagen wir mal jeder Buchstabe ist ein Object und ich würde jetzt TList nehmen.
Fürs verwalten der Buchstaben(habe ich einmal gemacht), jetzt wird ein Text geladen mit 20.0000 Objecten(Buchstaben, Grafiken), meinst du das wäre den User Zumutbar,
Wenn er diesen Text Bearbeiten möchte und jetzt pro Änderung 10 Sekunden warnte müsste ?

(ich möchte jetzt nicht darüber streiten/reden ob es sin macht das jeder Buchstabe ein Obect ist oder nicht,dafür habe ich einen andren Thread)

[theo]

Das TList schneller sein soll beim Hinzufügen/löschen/Updaten kann ich mir nicht vorstellen:
Wenn ich Hinzufügen oder Löschen möchte muss ich doch immer eine schleife starten vom Index der hinzugefügt oder gelöscht werden soll. um dann die Elemente nach und nach um ein Element zu verschieben. Das habe ich oft genug gemacht. Das TList auf ein Array basiert, gehe ich davon aus das die das genau so machen müssen.

Nein, so machen die das nicht. Du solltest die Geschwindigkeit von System.Move nicht unterschätzen.
Da ein Array auf einem zusammenhängenden Speicherbereich ist, kann man alles in einem Rutsch verschieben (Assembler/CPU-mässig). Siehe in "lists.inc" "TFPList.Insert".
Das geht schon verdammt schnell.
Schaut euch doch mal die FCL-Sourcen ein bisschen an. Ist doch alles da und gut gemacht. Siehe auch "fastmove.inc"

Ich kann mir nicht vorstellen das TList mit 20.000 Elemente umgehen kann. d.h.:

20000 Elemente verspeist TList zum Frühstück
Probier's doch aus und miss die Zeit.

Sagen wir mal jeder Buchstabe ist ein Object und ich würde jetzt TList nehmen.
Fürs verwalten der Buchstaben(habe ich einmal gemacht), jetzt wird ein Text geladen mit 20.0000 Objecten(Buchstaben, Grafiken), meinst du das wäre den User Zumutbar,
Wenn er diesen Text Bearbeiten möchte und jetzt pro Änderung 10 Sekunden warnte müsste ?

Natürlich nicht. Aber was ich von der "Ein Objekt pro Buchstabe" Idee halte weisst du ja.

[pluto]

Ja das weiß ich und darum geht das jetzt auch nicht. Aber ich bleibe dabei: TList ist einfach zu langsam. Das habe ich schon probiert. wie gesagt beim hinzufügen. der Texte bestandt glaube ich aus ca 1600 Buchstaben.

[theo]

Testen!! Hier:

Code: Alles auswählen

procedure TForm1.Button1Click(Sender: TObject);
var Li:TList;
var i,TestInt, Tick:Cardinal;
begin
Li:=TList.create;
 
Tick:=GetTickCount;
 
For i:=0 to 20000 do Li.Add(Pointer(TestInt)); //20000 hinzufuegen
 
For i:=0 to 20000 do Li.Insert(0,Pointer(TestInt)); //20000 am Anfang einfuegen, d.h. 20000 x alles hochschieben
 
Caption:=inttostr(GetTickCount-Tick);
 
Li.free;
end;

Also bei mir dauert das Adden ca 1ms und das Einfügen von 20000! Elementen am Anfang der Liste (schlimmster Fall) ca 700ms

[pluto]

Trotzdem ! ich verwende keine TList. Mich überzeugt das nicht. Ich habe schlechte Erfahrung gemacht gerade mit der Insert Funktion.

Evlt. lag es auch daran das ich nach jedem eintippen von einem neuen Buchstaben den Kompleten Text neu Zeichen musste.

[pluto]

wer hat den hier ein Beitrag editiert ? und welcher ?

[theo]

Trotzdem ! ich verwende keine TList. Mich überzeugt das nicht.

Wenn du den Messungen nicht traust, kann ich dir auch nicht helfen.

[pluto]

Ich habe sie wie gesagt einmal verwendet und auf meinem Rechner war es einfach zu langsam.