Ich habe eine TObjectlist mit mehreren 1000 Einträgen. Jedes Objekt darin entspricht einer Datei, und beinhaltet neben dem Dateipfad weitere Informationen wie. z.B. Dateigröße und Art der Datei.
Weiter habe ich ein Verzeichnis mit mehreren 1000 Dateien.

Ich möchte meine Liste mit der Verzeichnisstruktur synchronisieren. Die eine Richtung ist einfach. Ich überprüfe zu jedem Objekt, ob die Datei noch vorhanden ist -wenn nicht, lösche ich es aus der Liste.
Die andere Richtung macht mir etwas Probleme. Ich muss ja zu jeder Datei bestimmen, ob in meiner Liste schon ein Eintrag mit dem passenden Dateinamen vorhanden ist.
Sequentiell die Liste zu durchsuchen macht keinen Spass. 10.000 mal in einer 10.000-langen Liste alles durchzugehen dürfte zu lange dauern. Ich denke daran, die Liste zu Beginn nach Dateinamen (inkl.Pfad) zu sortieren, und dann darin jeweils eine Binärsuche zu starten.
Dann hätte ich die geschätzten 100.000.000 Operationen auf ungefähr 280.000 reduziert.

ABER: Wie ist der Zugriff auf Objectlist intern geregelt? Der Name sagt ja, dass es eine Liste ist. D.h. um auf das i-te Element zuzugreifen, benötigt man i Schritte. Für schnelles suchen müsste ich die Liste dann erst in ein Array umkopieren.
Oder hat TObjectlist auch Array-Character, und der Zugriff auf beliebige Elemente geht in konstanter Zeit? Wer weiss da was?

TObjectList baut auf einem Array auf. Ein kurzer Blick in die Sourcen verrät, dass die TObjectList auf TList aufbaut, was die Daten sequenziell speichert.

Aber ich würde mir überlegen, zum Suchen einen Binärbaum anzulegen. Bei 10.000 Einträgen hast du dort, von einer "Ausgewogenheit" (d.h. Symmetrie jedes Baumes und Unterbaumes) ausgegangen, maximal 14 Zugriffe, bis du das Element gefunden hast. Ob die Art der Daten eine ungefähre Ausgewogenheit ermöglicht, musst du dir vorher allerdings überlegen, im ungünstigen Fall hast du mit einem schlecht balancierten Binärbaum mehr Zugriffe.

Ok. Das baut also auf einem Array auf. Wozu dann einen Suchbaum daraus machen? Ein Suchbaum ist eine dynamische Struktur, die gegenüber der verketteten Liste den Vorteil hat, dass man in ihr schnell suchen (und finden) kann.
Wenn ich das aber schon in meinem List-Array-Zwitter TObjectlist machen kann, wozu dann den Baum generieren? Die Ausgewogenheit wär kein Problem, schließlich gibts ja AVL-Bäume. Aber mit Binärsuche in TObjectlist habe ich auch nur max. 14 Zugriffe. Vorausgesetzt, dass ein Zugriff auf ein beliebiges Element in konstanter Zeit möglich ist. Und das ist es ja scheinbar.

OK, wenn du deine Liste so sortierst, dass du sie binär durchsuchen kannst, dann brauchst du natürlich zum Suchen keine zusätzliche Datenstruktur anzulegen. Es sei denn, du willst dir pro Zugriff ein paar Takte sparen, da Zugriffe auf verkettete Strukturen schneller ist als Adressrechnung.

mal sehen, was ich da mache. Ich bin nämlich grade auf ein weiteres Problem gestoßen: Der Sortiervorgang dauert unter gewissen Umständen viel zu lange. Die Methode sort von TObjectlist ist scheinbar unbrauchbar. Zwar wird laut OH Quicksort verwendet, aber das Sortieren benötigt bei 4000 Objekten mal 21.000 (ok, ~N*logN), und mal 4.400.000 (nicht ok) Vergleiche. Allerdings habe ich noch nicht herausgefunden, woran das liegt, und welche Umstande zu der unakzeptablen Zeit führen.

Morgen überleg ich mal, ob ich nen Heap- oder Mergesort mit der Liste mache, oder ob ich sie in einen balancierten Baum kopiere, oder ob ich das einfach so lasse und darauf hoffe, dass der Quicksort nur selten lange benötigt...

Wenn du relativ selten sortieren und relativ öft auf dem sortierten Baum arbeitest, dann spielt die Sortierzeit ja nur eine geringe Rolle. Das würde ich auch noch bedenken.

Ich würde beim einfügen der Objekte schon die richtige Position in der Liste suchen. Mit einem Binary Search brauchst Du nur 17 Vergleiche um bei 50.000 Objekten dir richte Position zu finden. Damit sparst Du einen späteren Sortierlauf.

Gruß
KidPaddle

@UC-Chewie: Sortieren muss ich nur selten. Z.B. zu Beginn der Datenbanküberprüfung. Denn dann muss ich ja sehr oft ein Element suchen -> Besser vorher einmal was reinstecken, als ständig sequentiell suchen. Wenn der Sortiervorgang aber mehr als 10 Sekunden dauert, spielt das IMHO schon eine Rolle.

@KidPaddle: Das wär natürlich optimal. Allerdings ist ja TObjectlist ein Array (s.o.) und daher dauert das Einfügen eines Objectes an einer bestimmten Stelle etwas länger. Außerdem biete ich dem User die Möglichkeit, zwischendurch die Liste nach verschiedenen Kriterien zu sortieren (Artist, Titel, Album, etc.). Und das soll natürlich auch in fast Echtzeit gehen.

Du könntest dir ja auch für alle Sortierkriterien eigene Listen bzw. Bäume anlegen, die Zeiger auf die eigentlichen Daten in der Objektliste enthalten. Beim Hinzufügen eines neuen Objektes wird es an das Ende der Liste bzw. an eine freie Stelle innerhalb gehängt und gleichzeitig wird ein Zeiger darauf in allen Bäumen an die richtige Stelle eingefügt.

Da war doch im Forum der Hinweis auf die Suche in einer sortierten TStringlist.

Der bei Delphi eingebaute Suchalg. war das Halbierungsverfahren und als .Data kann die Liste deine Objekte genauso verwalten wie eine TObjectList. Auch alles was mit einer Anzeige zu tun hat, könnte davon profitieren, da das meist auch TStrings sind.

Das Thema hat sich mittlerweile erledigt. Die Frage war nur, ob TList eine Liste ist, oder ein Array. Denn in einer Liste bringt die Binärsuche (Halbierungsverfahren) nichts, da man nicht in einem Schritt auf ein beliebiges Elemnet zugreifen kann. Auch dann nicht, wenn die Liste sortiert ist. Da TList aber ein Array ist, kann ich dieses vorher einmalig sortieren und anschließend schnell darin suchen.