Performancefrage für ein einfaches Matching

[fisipjm]

Hi,

ich bin gerade dabei einen alten Code in bisschen zu überarbeiten und zu optimieren.
Im Code gibt es einen Part in dem ich aus einem String einen Index zurück erhalten muss.

Dabei geht es um ca. 100 Einträge die immer gleich aufgebaut sind.
String=Integer

Die Werte sind nie Doppelt, also immer Eindeutig auf beiden Seiten. Ich brauche im Programm lediglich die Möglichkeit den String einzugeben und dann den Integer Wert zurück zu erhalten. Derzeit verwende ich dafür ein TDecitionary und wollte einfach mal in die Runde hören wie ihr das macht und was das performanteste wäre.

Gibt ja noch viele andere möglichkeiten (Stringlist, Array, INI....)

Grüße
PJM

[stahli]

Die einfachste Lösung wäre m.E. eine Stringlist (mit Names und Values), die performanteste ein Dictionary (zumindest wenn es um größere Listen gehen würde).

Wenn Du eine funktionierende Lösung mit Dictionary hast, dann gibt es m.E. keinen Grund, das umzustellen.

[himitsu]

Bei TStringList und Array aka TArray<T> ist es das Selbe:
Wenn sie sortiert sind, dann geht die Suche schneller (je größer die Liste ist, um so schneller)

TArray.BinarySearch<T>(...) und vorher TArray.Sort<T>(...),
bzw. direkt beim Befüllen der Liste via TArray.BinarySearch und Insert die Einträge an der "richtigen" Stelle einfügen.

Das geht aber nur, wenn man nach "ganzen" Einträgen/Zeilen sucht.
Also bei der StringList nur mit IndexOf und Find, aber nicht für IndexOfName und Values[].
Beim Dictionary ist dagegen der "Name" in der sortieren Liste, ohne den Wert.



Es gibt im Delphi noch eine versteckte THashedStringList (IniFiles), bzw. sowas gibt es auch von anderen Entwicklern.



In diesem Fall also das Dictionary, da du ja nur den Namen suchen willst.
(bzw. alternativ die THashedStringList, welche Hash-Listen für Name und Value besitzt ... wobei "Value" hier falsch benannt ist, da das für die ganze "Line" gilt, also Name+Value)

Wenn sich aber sehr oft die Liste ändert, also im Verhältnis zum Ändern nicht wesentlich öfters gesucht wird, dann verbraucht der ständige Neuaufbau der HashListen unnötig viel Zeit.

[BigAl]

Bei 100 Einträgen würde ich mir da ehrlich gesagt keinen Kopf machen. Ich denke das egal welche Lösung genommen wird das ganze so schnell geht, dass mein keine Verzögerung merkt und das ganze drumherum (Eingabe auswerten, Wert ausgeben...) deutlich mehr Zeit braucht. Ich würde mich da erst ab 1000 oder mehr Einträgen mit beschäftigen.

Trotzdem: Ich denke TDictionary ist da schon ein sehr performanter (wenn auch aufwändiger) Ansatz. Eine sortierte TStringList wäre mein persönlicher Favorit. Man kann da schön mit Value[<name>] die Werte abrufen. Weiterhin gibt es da alles was mach braucht wie Sort, IndexOfName, KeyNames usw... Erzeugt grundsätzlich ein sehr einfach zu lesenden Code...

Alex

[himitsu]

Es kommt darauf an, wie oft es gemacht wird.

Auch "nur" 20 Millisekunden mehr können schlimm werden, wenn man es eine Million Mal macht.

[BigAl]

Zitat:

Zitat von himitsu (Beitrag 1507213)

Es kommt darauf an, wie oft es gemacht wird.

Auch "nur" 20 Millisekunden mehr können schlimm werden, wenn man es eine Million Mal macht.

Ich bezweifle, dass 100 Einträge eine Million mal hintereinander abgefragt werden. Grundsätzlich denke ich, dass der Wert in deutlich weniger als einer Millisekunde zur Verfügung steht, egal wie man es macht (außer man fügt Sleeps ein :-)). Aber ohne genauere Hintergründe zu kennen sind das halt alles Annahmen. Und ja, auch verbringe manchmal (zu viel) Zeit damit Dinge zu optimieren, die es nicht wert sind...

Gruß
Alex

[himitsu]

Bei 100 Einträgen, braucht eine binäre Suche maximal 7 Vergleiche,
während eine sequentielle Suche durchschnittlich 50, aber bis zu 100 Vergleiche benötigt.

Das wäre somit locker 90% schneller.



Bei 1000 Einträgen sind es bereits maximal 10 zu bis zu 1000 Vergleiche. (99%)

Als HashList sind Integer-Vergleiche (ein CPU-Register) gegen String-Vergleiche. (optimiert/sortiert oder als Baum wären es 10 Integer, bzw. unoptimiert 1000 Integer, gegen 10 bzw. 1000 umständliche Strings)

[BigAl]

Hallo himitsu,

ist schon klar. Mir geht es ja nur darum ab wann es wert ist zu optimieren. Ich habe gerade mal eine normale StringListe mit 100 random strings und 100 random integers als Wertepaar generiert. Darauf habe ich dann 10000 mal random gesucht und das Ergebnis (Value) dann noch in einen Integer zur Weiterverarbeitung gewandelt. Das ganze braucht auf meinem (durchschnittlich schnellen Rechner) ca. 1 bis 2 µs (Microsekunden!!!) für eine komplette Suche...

[himitsu]

Wie schon gesagt wurde, scheint das Dictionary ja bereits ausreichend optimal zu sein.

Hier lässt sich nur durch die Wahl der "passenden" Standardkomponente, in vielen Fällen, bereits ein halbwegs optimales Ergebnis erreichen.
Eben Dictionary (oder THashedStringList, gegenüber einer TStringList, ohne dass man Mehraufwand hat.

[Stevie]

Generell immer erstmal die Frage: ist es schnell genug (schnell genug, kannst nur du, bzw die Benutzer beurteilen), bei ner GUI Anwendung ist schnell genug etwas anderes als auf nem Server, wo zigtausend Anfragen einprasseln.

Lautet die Antwort "nein", lautet die nächste Aufgabe: was genau verbraucht hier die Zeit (idR mit einem Profiler herauszufinden). Stellt sich dann heraus, dass es der vermutete Teil ist (Spoiler: meistens ist es das nicht sondern etwas unerwartetes, zumindest für die meisten Entwickler, die nicht gerade Profiling als Hauptbeschäftigung betreiben)

Zu der konkreten Frage hier ist es durchaus interessant, a) wie lang die entsprechenden Strings sind und b) wie viele vorhanden sind bzw und ob diese beiden Zahlen statisch sind oder dynamisch, sprich, sind es fest immer 100 Einträge oder können es auch mal 100000 werden. Denn daraus ergibt sich ob man ein O(1) haben möchte oder ein O(log n).

Bisschen Lektüre zu dem Thema:
https://www.delphitools.info/2015/03...d-or-unsorted/
https://www.delphitools.info/2015/03...d-vs-unsorted/

Interessanter Fakt am Rande:
Seit Delphi 11 wird im TDictionary FNV1a genutzt und nicht mehr BobJenkins