String in TStringList finden verschnellern?

[a.def]

In meinem Programm werden zwei StringListen mit mal mehr, mal weniger Einträgen erzeugt. Das kann bis in die Tausende und Zehntausende, auch Hunderttausende gehen.

Ich prüfe an einer bestimmten Stelle, ob ein Eintrag X aus Liste 1 in Liste 2 vorhanden ist. Das mache ich so

Delphi-Quellcode:

// Beispiel:
// sTmp ist 'C:\1\2\3\4.txt';
// List enthält ("Liste 2)
// - C:\1.txt
// - C:\1\2.txt
// - C:\1\2\3.txt
// - C:\1\2\3\4.txt

function IndexOfListObjects(const sTmp: string; List: TStringList): Integer;
begin
 for Result := 0 to List.Count - 1 do
  if sTmp = PFileListEntry(List.Objects[Result])^.sFileName then
   Exit;

 Result := -1;
end;

So speichere ich zuvor in die Liste wenn diese erstellt wird

Delphi-Quellcode:

// Record erzeugen mit New()
// ...
List.AddObject(aFileListEntry.sFileName, Pointer(aFileListEntry));

PFileListEntry ist ein Rekord mit ein paar Informationen wie Dateiname und Attributen usw.

Diese Prüfung "IndexOfListObjects" wird bei jeder Iteration von "Liste 1" durchgeführt.
Das dauert relativ lange. Kann man das nicht irgendwie verschnellern?

[nahpets]

Ist die Liste sortiert?

Wenn ja, versuch' es mal mit 'ner binären Suche.

Kannst Du die Liste sortieren?
Wenn ja, wie lange dauert das?

Wäre ggfls. ein Sortieren der Liste und dann anschließend eine binäre Suche insgesamt schneller als Dein bisheriges Vorgehen?

Was steht in der Stringliste selbst drin?
Du suchst ja in den Objekten.
Könnte eine Suche mit List.IndexOf(sTmp) ggfls. schneller sein, sofern Du dort bereits einen sinnvoll zu suchenden Inhalt haben solltest?

Wenn als Beispiel in PFileListEntry(List.Objects[0])^.sFileName C:\1\2\3\4.txt stehen würde, was stände dann in List[0] ?

[Fritzew]

Hallo

da Du ja den Filenamen schon in der Liste stehen hast

List.AddObject(aFileListEntry.sFileName, Pointer(aFileListEntry)); Könntest Du doch einfach mit

result := List.indexof(sTemp) danach suchen Wenn Die Liste dann auch noch sortiert ist geht das relativ schnell

ansonsten benutze doch ein Dictionary

[a.def]

Zur Beantwortung deiner Fragen:

- die Liste war nicht sortiert. Ich habe nun nach dem Create der Liste ein Sorted := True; angehangen.

- das Benutzen von IndexOf(sTmp) war deutlich langsamer als das Suchen in den Objekten.

Zitat:

Wenn als Beispiel in PFileListEntry(List.Objects[0])^.sFileName C:\1\2\3\4.txt stehen würde, was stände dann in List[0] ?

In List[0] wäre dann im besten Fall genau derselbe String.

[p80286]

Zitat von a.def:

Zur Beantwortung deiner Fragen:

- die Liste war nicht sortiert. Ich habe nun nach dem Create der Liste ein Sorted := True; angehangen.

in unsortierten Listen (Arrays etc.) suchen, ist grundsätzlich nicht empfehlenswert.

Zitat von a.def:

- das Benutzen von IndexOf(sTmp) war deutlich langsamer als das Suchen in den Objekten.

Das sollte aber der pure Zufall gewesen sein.

Statt Indexof könntest Du auch Find nutzen, oder aber wie Stefan schon vorgeschlagen hat, bau Dir eine Binäre Suche, die könntest Du dann für Deine speziellen Zwecke anpassen.

Gruß
K-H

[nahpets]

Ok, mit Sorted := True ist der Inhalt also aufsteigend sortiert und damit kannst Du dann binär suchen.

Grober Überblick: https://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

Hier im Forum mal suchen: http://www.delphipraxis.net/dp_searc...ch_matchmode=0

@p80286
IndexOf ist nicht wirklich schnell, da es in unsortierten Listen letztlich auch in 'ner While-Schleife alle Einträge abfragt, bis was gefunden wurde.
Entspricht daher vom Zeitaufwand vermutlich in etwa der For-Schleife.

In 'ner sortierten Liste wird allerdings mit Find gesucht.

@a.def
Durch das Sorted := True könnte sich damit die Laufzeit für IndexOf verändert haben.

[himitsu]

IndexOf und Find sollte doch gleich schnell sein?
Und ja, sortieren hilft (Sorted=True), denn dann wird eine andere Suchmethode verwendet.
> TArray.BinarySearch

Alternativ eine HashList.
TDictionary?

[a.def]

Mich würde mal interessieren, warum eine sortierte Liste schneller durchsucht werden kann als eine unsortierte?
Ob da jetzt 1 Millionen sortierte oder unsortierte Einträge sind... es sind 1 Millionen.

[DeddyH]

Weil man in einer sortierten Liste eben nicht mehr alle Einträge sequentiell durchsuchen muss. Schau Dir doch einfach einmal an, wie eine binäre Suche funktioniert ("Pieksen" in die Mitte, vergleichen und eine Hälfte ignorieren, das so lange, bis der gesuchte Eintrag gefunden wurde oder es keine "Mitte" mehr gibt -> kein Treffer).

[stahli]

Man fängt in der Mitte an und schaut, ob der Suchwert größer oder kleiner ist.
Je geht man zur Mitte der kleineren oder größeren Hälfte und dann weiter bis zum Treffer.
Dann erhält man nach einigen Zyklen das Ergebnis oder die Position, an der der neue Eintrag eingefügt werden müsste.

Das ist die binäre Suche.