Delphi-PRAXiS
Seite 1 von 7  1 23     Letzte » 

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Programmieren allgemein (https://www.delphipraxis.net/40-programmieren-allgemein/)
-   -   String in TStringList finden verschnellern? (https://www.delphipraxis.net/191366-string-tstringlist-finden-verschnellern.html)

a.def 7. Jan 2017 15:38


String in TStringList finden verschnellern?
 
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 7. Jan 2017 16:09

AW: String in TStringList finden verschnellern?
 
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
Delphi-Quellcode:
PFileListEntry(List.Objects[0])^.sFileName
Delphi-Quellcode:
C:\1\2\3\4.txt
stehen würde, was stände dann in
Delphi-Quellcode:
List[0]
?

Fritzew 7. Jan 2017 16:10

AW: String in TStringList finden verschnellern?
 
Hallo

da Du ja den Filenamen schon in der Liste stehen hast

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

Delphi-Quellcode:
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 7. Jan 2017 16:12

AW: String in TStringList finden verschnellern?
 
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 7. Jan 2017 16:45

AW: String in TStringList finden verschnellern?
 
Zitat:

Zitat von a.def (Beitrag 1358325)
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:

Zitat von a.def (Beitrag 1358325)
- das Benutzen von IndexOf(sTmp) war deutlich langsamer als das Suchen in den Objekten.

Das sollte aber der pure Zufall gewesen sein.

Statt
Delphi-Quellcode:
Indexof
könntest Du auch
Delphi-Quellcode:
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 7. Jan 2017 16:54

AW: String in TStringList finden verschnellern?
 
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 7. Jan 2017 16:56

AW: String in TStringList finden verschnellern?
 
IndexOf und Find sollte doch gleich schnell sein?
Und ja, sortieren hilft (Sorted=True), denn dann wird eine andere Suchmethode verwendet.
> Delphi-Referenz durchsuchenTArray.BinarySearch

Alternativ eine HashList.
TDictionary?

a.def 7. Jan 2017 16:57

AW: String in TStringList finden verschnellern?
 
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 7. Jan 2017 17:05

AW: String in TStringList finden verschnellern?
 
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 7. Jan 2017 17:09

AW: String in TStringList finden verschnellern?
 
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.


Alle Zeitangaben in WEZ +1. Es ist jetzt 10:54 Uhr.
Seite 1 von 7  1 23     Letzte » 

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz