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 von 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.

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)