AW: String in TStringList finden verschnellern?
Zitat:
Oder ist es mit 8 Uhr noch zu früh für mich...? :oops: |
AW: String in TStringList finden verschnellern?
Zitat:
Ich kenne es nur nicht. Ist das in etwas so? http://www.delphipraxis.net/94559-ei...onary-map.html 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. |
AW: String in TStringList finden verschnellern?
Zitat:
Delphi-Quellcode:
(gleich 0, kleiner 0, größer 0)
V = A - B
CompareValue 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. |
AW: String in TStringList finden verschnellern?
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 |
AW: String in TStringList finden verschnellern?
Das liegt daran, dass du ausgerechnet die grausamste und sinnloseste Implementation einer Hashlist erwischt hast.
Delphi-Quellcode:
Vor jeder einzelnen Suchanfrage werden ALLE Hashs neu berechnet. :wall:
//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; Das muß zwangsläufig langsamer sein. |
AW: String in TStringList finden verschnellern?
Zitat:
Ich habe das jetzt mal mit IndexOf statt Find gemacht und da ist die HashedStringList schneller als die normale (trotz Neuberechnung der Hashes) |
AW: String in TStringList finden verschnellern?
Zitat:
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. |
AW: String in TStringList finden verschnellern?
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:
Hier fehlt zum Beispiel noch die Prüfung, ob der Suchbegriff überhaupt in der Stringliste vorkommt, also ist
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;
Delphi-Quellcode:
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; |
AW: String in TStringList finden verschnellern?
Zitat:
Gruß K-H |
AW: String in TStringList finden verschnellern?
Zitat:
Delphi-Quellcode:
eine binäre Suche durchführt und
Find
Delphi-Quellcode:
direkt Find aufruft, wenn
IndexOf
Delphi-Quellcode:
gesetzt ist.
Sorted
Daraus folgt a) daß
Delphi-Quellcode:
nur dann funktionieren kann, wenn
Find
Delphi-Quellcode:
gesetzt wurde, und b)
Sorted
Delphi-Quellcode:
immer funktioniert c)
IndexOf
Delphi-Quellcode:
im Falle von
IndexOf
Delphi-Quellcode:
wegen der binären Suche in
Sorted
Delphi-Quellcode:
schon recht schnell sein sollte.
Find
Bleiben noch die Optimierungsmöglichkeiten in
Delphi-Quellcode:
, das sowohl von
CompareStrings
Delphi-Quellcode:
als auch von
Find
Delphi-Quellcode:
im Falle von
IndexOf
Delphi-Quellcode:
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.
Sorted = false
Folglich sollte das beste Ergebnis erzielt werden, wenn die Stringlist mit folgenden Einstellungen betrieben wird:
Delphi-Quellcode:
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.
Sorted := true;
CaseSensitive := true; UseLocale := false; 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. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 13:46 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