AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein String in TStringList finden verschnellern?

String in TStringList finden verschnellern?

Ein Thema von a.def · begonnen am 7. Jan 2017 · letzter Beitrag vom 10. Jan 2017
Antwort Antwort
Seite 1 von 7  1 23     Letzte » 
a.def
(Gast)

n/a Beiträge
 
#1

String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 15:38
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?

Geändert von a.def ( 7. Jan 2017 um 15:42 Uhr)
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#2

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:09
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] ?
  Mit Zitat antworten Zitat
Fritzew

Registriert seit: 18. Nov 2015
Ort: Kehl
678 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:10
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
Fritz Westermann
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#4

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:12
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.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#5

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:45
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.

- 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
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#6

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:54
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.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.014 Beiträge
 
Delphi 12 Athens
 
#7

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:56
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?
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests

Geändert von himitsu ( 7. Jan 2017 um 16:59 Uhr)
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#8

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 16:57
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.
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.533 Beiträge
 
Delphi 11 Alexandria
 
#9

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 17:05
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).
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli
Online

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.336 Beiträge
 
Delphi 11 Alexandria
 
#10

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 17:09
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.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:22 Uhr.
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