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 3 von 7     123 45     Letzte » 
EmWieMichael

Registriert seit: 28. Mär 2012
31 Beiträge
 
#21

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 07:04
...
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
...
Täusche ich mich, oder werden bei dieser Rechnung die Vergleiche mit '=' vergessen? Ich muss doch nach jeder Halbierung zwei Vergleiche anstellen: '=' und ('<' oder '>').
Oder ist es mit 8 Uhr noch zu früh für mich...?
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#22

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 10:59
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...
Ich wehre mich doch nicht dagegen
Ich kenne es nur nicht.

Ist das in etwas so? Einfache String-/String-Beziehung (Dictionary / Map)
Wenn ja, dann bedeutet das ja "doppelte Buchführung" wenn ich das richtig sehe. Denn man braucht einen linken und rechten Teil um ein Paar zu bilden.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 11:13
Täusche ich mich, oder werden bei dieser Rechnung die Vergleiche mit '=' vergessen? Ich muss doch nach jeder Halbierung zwei Vergleiche anstellen: '=' und ('<' oder '>').
Rein "logisch" nur eine mathematische Rechnung.
V = A - B (gleich 0, kleiner 0, größer 0)
Delphi-Referenz durchsuchenCompareValue
Dann weiß man sofort ob größer, kleiner oder gleich.

Aber aus diesem Grund sind Hash-Listen schneller, da dort je Wert nur ein "Vergleich" nötig ist, während bei Strings ja jedes einzelne Char verglichen werden muß.

Die genaue Anzahl der physischen Vergleiche, im Bytecode (Assembler) oder gar in der CPU, will man besser nicht wissen.
Für einen Vergleich zweier Suchalgorithmen reicht es, wenn man die ungefähre Anzahl der logischen Vergleichsoperationen kennt.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014

Geändert von himitsu ( 8. Jan 2017 um 11:22 Uhr)
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#24

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 11:23
Bei einem ganz einfachen Test war bei mir die normale StringList schneller

Delphi-Quellcode:
procedure TForm1.Button2Click(Sender: TObject);
var
 sl: THashedStringList;
 i, X: Integer;
 Watch: TStopwatch;
begin
 sl := THashedStringList.Create;

 sl.Sorted := True;
 for i := 0 to 49999 do
  sl.Add(TStringUtils.RandomString(60));

 sl.Add('ABCABCABC');

 for i := 0 to 49999 do
  sl.Add(TStringUtils.RandomString(60));

 Watch := TStopwatch.Create;
 Watch.Start;

 for i := 0 to sl.Count - 1 do
  begin
   sl.Find('ABCABCABC', X); // Absichtlich kein Break, damit alles verglichen wird
  end;

 Watch.Stop;
 ShowMessage(IntToStr(Watch.ElapsedMilliseconds) + 'ms');
 sl.Free;
end;

// StringList: ~180ms
// HashedList: ~200ms
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 11:44
Das liegt daran, dass du ausgerechnet die grausamste und sinnloseste Implementation einer Hashlist erwischt hast.
Delphi-Quellcode:
//Unit IniFiles

function THashedStringList.IndexOf(const S: string): Integer;
begin
  UpdateValueHash;
  if not CaseSensitive then
    Result := FValueHash.ValueOf(AnsiUpperCase(S))
  else
    Result := FValueHash.ValueOf(S);
end;
Vor jeder einzelnen Suchanfrage werden ALLE Hashs neu berechnet.
Das muß zwangsläufig langsamer sein.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#26

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 12:04
Vor jeder einzelnen Suchanfrage werden ALLE Hashs neu berechnet.
Wenn die HashedStringList mit diesem groben, sagen wir mal, "Fehler" diese geschwindigkeit erzielt (nur 20ms langsamer als die normale in meinem Beispiel), dann muss die ja super schnell sein, wenn dieser "Fehler" nicht ist.

Ich habe das jetzt mal mit IndexOf statt Find gemacht und da ist die HashedStringList schneller als die normale (trotz Neuberechnung der Hashes)

Geändert von a.def ( 8. Jan 2017 um 12:06 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von haentschman
haentschman
Online

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

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 12:37
Zitat:
Ist das in etwas so?
Nöö...

Schau mal hier: http://docwiki.embarcadero.com/Libra...ns.TDictionary

eine der Varianten...TryGetValue: http://docwiki.embarcadero.com/Libra...ry.TryGetValue
... gibt den Value zurück wenn Key gefunden wird.
  Mit Zitat antworten Zitat
nahpets

Registriert seit: 11. Okt 2006
2.952 Beiträge
 
Delphi 7 Professional
 
#28

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 12:45
Wenn man in IndexOf und Find reinschaut, sieht man, dass da noch ziemlich vieles gemacht wird, um zum Vergleichsergebnis zu kommen.

Hier wird aber doch "nur" ein einfacher Vergleich auf Übereinstimmung von Zeichenfolgen in 'ner sortierten Stringliste benötigt.

Wie wäre es denn, hier einfach mal 'ne eigene Suchroutine zu schreiben, der die Stringliste übergeben wird und die als Rückgabewert den Index des gesuchten Eintrages der Stringliste liefert.

Ungetestet und nur hingedaddelt, daher ohne jegliche Garantie für irgendwas, sondern nur als Idee für's eigene Ausprobieren:
Delphi-Quellcode:
function BinSearch(Suche : String; Start : Integer; Ende : Integer; sl : TStringList) : Integer;
var
        Mitte : Integer;
begin
  Mitte := Start + ((Ende - Start) div 2);
  if Suche <= sl[Mitte] then Result := BinSearch(Suche, Start, Mitte, sl)
  else Result := BinSearch(Suche, Mitte, Ende, sl);
end;
Hier fehlt zum Beispiel noch die Prüfung, ob der Suchbegriff überhaupt in der Stringliste vorkommt, also ist

sl[BinSearch('ASDF',0,sl.Count - 1,sl) = 'ASDF';

Könnte daraus eventuell dann sowas werden?
Delphi-Quellcode:
function IndexOfListObjects(const sTmp: string; List: TStringList): Integer;
begin
 Result := BinSearch(sTmp,0,List.Count - 1,List);
 if List[Result] <> sTmp then Result := -1;
end;
Stephan
Weil die Lichtgeschwindigkeit höher als die Schallgeschwindigkeit ist, hält man viele Leute für helle Köpfe, bis man sie reden hört.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

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

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 15:07
Aber aus diesem Grund sind Hash-Listen schneller, da dort je Wert nur ein "Vergleich" nötig ist, während bei Strings ja jedes einzelne Char verglichen werden muß.
Naja nicht unbedingt, "damals" haben wir die Strings in 16-Bit Werte zerhackt, und diese dann verglichen, da konnte man gegenüber den 8-Bit Vergleichen knappe 50% herausholen. Mit 32-Bit oder gar 64-Bit kann man da gut Gas geben. Und die hash-Berechnung fällt nicht an.

Gruß
K-H
Programme gehorchen nicht Deinen Absichten
sondern Deinen Anweisungen
Do it with Delphi Programming
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe
Online

Registriert seit: 20. Jan 2006
Ort: Lübbecke
5.096 Beiträge
 
Delphi 10.2 Tokyo Architect
 
#30

AW: String in TStringList finden verschnellern?

  Alt 8. Jan 2017, 15:08
Wenn man in IndexOf und Find reinschaut, sieht man, dass da noch ziemlich vieles gemacht wird, um zum Vergleichsergebnis zu kommen.
Insbesondere sieht man, daß Find eine binäre Suche durchführt und IndexOf direkt Find aufruft, wenn Sorted gesetzt ist.

Daraus folgt a) daß Find nur dann funktionieren kann, wenn Sorted gesetzt wurde, und b) IndexOf immer funktioniert c) IndexOf im Falle von Sorted wegen der binären Suche in Find schon recht schnell sein sollte.

Bleiben noch die Optimierungsmöglichkeiten in CompareStrings , das sowohl von Find als auch von IndexOf im Falle von Sorted = false aufgerufen wird. Da CompareStrings virtuell ist müssen wir hier die Implementierung in TStringList heranziehen. Darin wird je nach Kombination der Properties UseLocale und CaseSensitive CompareStr oder CompareText bzw. der Ansi-Pendants aufgerufen. Letztere bemühen jeweils eine Funktion aus der Windows-API und sind somit potentiell langsamer als ihre nativen Vettern. Diese beiden (CompareStr und CompareText) sind aus dem Fastcode-Projekt übernommen worden und somit potentiell auch nicht die langsamsten. Da die Text-Variante noch die Groß/Klein-Schreibung berücksichtigt (in dem sie sie ignoriert), ist diese potentiell noch etwas langsamer als CompareStr, daß einen direkten Vergleich durchführt.

Folglich sollte das beste Ergebnis erzielt werden, wenn die Stringlist mit folgenden Einstellungen betrieben wird:

Delphi-Quellcode:
Sorted := true;
CaseSensitive := true;
UseLocale := false;
Trotzdem kann das stumpfe Iterieren durch alle Strings mit einem direkten Vergleich durchaus deutlich schneller sein, als das Find. Im Gegensatz zu CompareString, daß einen Ordnungsvergleich (kleiner, gleich, größer) durchführt, wird bei einem direkten Vergleich eben nur auf Gleichheit getestet. Da Strings aber referenzgezählte Objekte sind, kann bei diesem Vergleich als erstes geprüft werden, ob es sich um dasselbe Objekt handelt und nicht nur um einen String mit demselben Inhalt.

Selbst bei mehreren Millionen Einträgen kann der Brute-Force Ansatz immer noch schneller sein. Man sollte das also mit realen Daten testen, bevor man blind eine bestimmte Methode einsetzt.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  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 16:27 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