AGB  ·  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 2 von 7     12 34     Letzte » 
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
32.175 Beiträge
 
Delphi XE3 Professional
 
#11

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 17:11
Das Tempo ist da logarithmisch und nicht linear.

* jeden Eintrag durchsuchen, also im Durchschnitt 50% aller Einträge, bis man was findet.
* die binäre Suche ist für Sortiertes optimiert, da man beim Vergleich sofort weiß, ob man was getroffen hat und wenn nicht, ob es vor oder hinter dem Eintrag zu finden ist

bei 1000 Einträgem
* linear = durchschnittlich 500 Vergleiche
* binär = maximal 10 Vergleiche


Zusätzlich noch CaseSensitive=True.
Dateinamen sind zwar CaseSensitive=False, aber wenn du außerhalb AnsiUpperCase/FileNameUpperCase machst, dann muß das die Liste nicht mehr bei jedem Eintrag machen.
Beim Dictionary gibt es auch welche, die CaseInsensitiv den Hash berechnen und das dann ebenfalls nicht mehr bei jedem Eintrag machen müssen, während der Suche.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
a.def

Registriert seit: 18. Nov 2016
435 Beiträge
 
Delphi XE8 Professional
 
#12

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 17:26
Zitat:
Man fängt in der Mitte an und schaut, ob der Suchwert größer oder kleiner ist.
Das erinnert mich an ein kleines Spiel, welches ich zu Schulzeiten in Java geschrieben habe. Dabei ging es um das Erraten einer Zahl.

Nun habe ich es verstanden.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
32.175 Beiträge
 
Delphi XE3 Professional
 
#13

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 18:40
Darum auch Binär (Zwei), weil man dort immer alles halbiert.

Die maximal nötigen Vergleiche, bis man einen Eintrag gefunden hat, sind auch "zufällig" immer Zweiterpotenzen.

...
65 bis 128 = maximal 7 Vergleiche
129 bis 256 Werte = maximal 8 Vergleiche
257 bis 512 Werte = maximal 9 Vergleiche
513 bis 1024 Werte = maximal 10 Vergleiche
...
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
mjustin

Registriert seit: 14. Apr 2008
2.344 Beiträge
 
Delphi 2009 Professional
 
#14

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 19:06
Wäre eine Lösung mit TDictionary (Generics.Collections) nicht wesentlich schneller, wenn die Anzahl wie angegeben in die Hunderttausende geht?
Michael Justin
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
32.175 Beiträge
 
Delphi XE3 Professional
 
#15

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 19:13
Wurde schon erwähnt.

TDictionary ist eine sortierte Hash-Liste mit binärer Suche.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
5.300 Beiträge
 
Delphi 7 Personal
 
#16

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 19:28
In 'ner sortierten Liste wird allerdings mit Find gesucht.
Gleicher Aufruf, unterschiedliches Verhalten, das liebe ich.

Gruß
K-H
Programme gehorchen nicht Deinen Absichten
sondern Deinen Anweisungen
Do it with Delphi Programming
  Mit Zitat antworten Zitat
a.def

Registriert seit: 18. Nov 2016
435 Beiträge
 
Delphi XE8 Professional
 
#17

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 19:44
Was haltet ihr denn davon. Ist das eine Lösung?
Speeding Up Delphi's TStringList.IndexOf

Ich nutze nun

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

 if not List.Find(sTmp, Result) then
  Result := -1;
end;
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
32.175 Beiträge
 
Delphi XE3 Professional
 
#18

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 20:03
Zitat:
Delphi-Quellcode:
function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;
Wenn deine Liste also Sortiert ist, ergibt es das.
Delphi-Quellcode:
function TStringList.IndexOf(const S: string): Integer;
begin
  if not Find(S, Result) then
    Result := -1;
end;
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
a.def

Registriert seit: 18. Nov 2016
435 Beiträge
 
Delphi XE8 Professional
 
#19

AW: String in TStringList finden verschnellern?

  Alt 7. Jan 2017, 20:24
Einziger Unterschied den ich gerade erkennen konnte ist, dass die offizielle Fassung von Find () CompareStrings aufruft, die inoffizielle CompareStr().
Sonst ist alles gleich. Hätte ich mal vorher gucken sollen.
  Mit Zitat antworten Zitat
Benutzerbild von haentschman
haentschman
Online

Registriert seit: 24. Okt 2006
Ort: Seifhennersdorf / Sachsen
3.356 Beiträge
 
Delphi 10.1 Berlin Professional
 
#20

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 07:28
Moin...

Was ich nicht verstehe, das du dich gegen das angesprochene TDictionary, jedenfalls habe ich es nicht gesehen, wehrst... Das ist genau das für den Einsatzzweck gut ist... als das rumgeeiere mit der Stringlist...
  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:

Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:56 Uhr.
Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2017 by Daniel R. Wolf