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

[fisipjm]

Okay,
zunächst mal Sorry für den geringen Informationsgehalt. Ich versuch mal ein bischen Licht ins dunkel zu bringen.

Die Funktion welche ich aktuell versuche zu optimieren gibt es eigentlich schon. Wir setzen eine Komponente in Delphi ein um auf einen Applikationsserver eines Drittherstellers zuzugreifen, der wiederrum auf eine MSSQL geht.
Dort gibt es eine Funktion zum Feldwerte lesen. Der Aufruf funktioniert grob so:

Delphi-Quellcode:

ThirdPartyComponent.Select('Select Feldname From Tabelle');
ThirdPartyComponent.GetFieldvalue('Feldname');

Ich hab jetzt durch Zufall herausgefunden, dass der Aufruf des Herstellers sich einen Fuß ins Ohr schafft. zu dem Zeitpunkt wo ich den Feldwert aufrufen kann, liegt mir nämlich eigentlich schon das gesamte Ergebnis der ganzen Abfrage als 2 Dimensionales OleVariant Array vor. Beim Aufruf der GetFieldvalue Funktion wird der Wert nochmal auf der Applikationsschicht abgefragt, allerdings nicht in der DB sondern nur in einem internen Cache. Also auch kein Vorteil zum Thema Datenaktualität.

Das Olevariant Array muss ich nun eben mit

Delphi-Quellcode:

Olevariant[Spaltennummer,Zeilennummer]

aufrufen.

Aufrufzeit für einen Feldwert mit 4181 Zeilen = 4310ms (Komponentenfunktion)
Aufrufzeit für einen Feldwert mit 4181 Zeilen = 1ms (eigene Funktion)

soweit ja schon mal subi :-) Werfe ich jetzt in die SQL Abfrage noch ein 2. Feld rein dann wird aus der 1ms schon 50ms usw.
Das liegt halt daran, dass ich die Komponente gerne kapseln will um nicht den Index aufrufen zu müssen, sondern weiter den Feldwert benutzen kann. Welchen Index der Feldwert hat schreib ich mir also einmalig beim ersten aufruf in das Dictionary und kann dann später in meiner funktion mit der gleichen Sytax den Feldwert wieder mit Namen aufrufen. Das Suchen scheint aber eben mit jedem Eintrag im Dictionary entsprechend länger zu dauern. Das wollte ich gerne ein bisschen einbremsen :-D

Ich hoffe damit wird klarer was ich versuche zu erreichen.

[freimatz]

Klarer ja, klar genug zweifelhaft.
Ich bin mir aber sicher dass für den Geschwindigkeitsnachteil das SQL schuld ist und nicht das TDictionary.

[fisipjm]

Zitat:

Zitat von freimatz (Beitrag 1507258)

Klarer ja, klar genug zweifelhaft.
Ich bin mir aber sicher dass für den Geschwindigkeitsnachteil das SQL schuld ist und nicht das TDictionary.

Nö, der SQL Server ist nicht Teil der Geschwindigkeitsmessung. Die beginnt erst nachdem die Daten schon abgeholt wurden.
Welche infos fehlen noch um an ein klar genug ran zu kommen?

[Stevie]

Liest sich ähnlich zu der

Delphi-Quellcode:

FieldByName

Problematik, wenn man das in einer Schleife immer benutzt anstatt vor der Schleife einmal die Felder über FieldByName zu holen, um dann darauf zuzugreifen.

Wie macht man Dinge schneller? Man vermeidet redundante Arbeit - in diesem Fall das ermitteln des Indexes per Name indem man es einmal vor der Schleife macht.

[Uwe Raabe]

Zitat:

Zitat von Stevie (Beitrag 1507265)

Liest sich ähnlich zu der

Delphi-Quellcode:

FieldByName

Problematik, wenn man das in einer Schleife immer benutzt anstatt vor der Schleife einmal die Felder über FieldByName zu holen, um dann darauf zuzugreifen.

Das ist aber mittlerweile auch nicht mehr ganz so problematisch wie früher, seitdem das über ein Dictionary realisiert wird.

Delphi-Quellcode:

function TFields.FindField(const FieldName: string): TField;
begin
  FDict.TryGetValue(AnsiLowerCase(FieldName), Result);
end;

[himitsu]

Zum Glück setzt dieses TDictionary<K,V> das Value auch dann, wenn nichts gefunden wurde, sonst wäre das Result von FindField nicht initialisiert, weil niemand das Result vom TryGetValue auswertet. :stupid:

[Stevie]

Zitat:

Zitat von Uwe Raabe (Beitrag 1507268)

Das ist aber mittlerweile auch nicht mehr ganz so problematisch wie früher, seitdem das über ein Dictionary realisiert wird.

Sind aber trotzdem bei 4181 Zeilen mit 2 Feldern 8360 unnütze Aufrufe. Die Quintessenz des Threads hier war bisher die Frage "wie bekomm ich das matching schneller" und ich hab einfach in den Raum gestellt "mach es nicht schneller, sondern lass es weg".

P.S. Bei dem

Delphi-Quellcode:

AnsiLowerCase

anstatt eines case insensitiven EqualityComparers (und ich mein nicht den aus System.Generics.Defaults, der ist nämlich auch Schrott, da er nix anderes als AnsiLowerCase macht) dreht sich mir übrigens der Magen um.

[freimatz]

Zitat:

Zitat von fisipjm (Beitrag 1507264)

Zitat:

Zitat von freimatz (Beitrag 1507258)

Klarer ja, klar genug zweifelhaft.
Ich bin mir aber sicher dass für den Geschwindigkeitsnachteil das SQL schuld ist und nicht das TDictionary.

Nö, der SQL Server ist nicht Teil der Geschwindigkeitsmessung. Die beginnt erst nachdem die Daten schon abgeholt wurden.
Welche infos fehlen noch um an ein klar genug ran zu kommen?

Deine Aussage "Werfe ich jetzt in die SQL Abfrage noch ein 2. Feld rein dann wird aus der 1ms schon 50ms usw." lies mich zum Schluß kommen dass da was mit SQL dabei ist.
Wie die Kollegen hier auf FieldByName kommen erschließt sich mir nicht. Wenn denen das klar ist reicht das ja. Kompetentere wie z.B. Uwe und Stevie lassen sich eh nicht finden. ;-)

[fisipjm]

Zitat:

Zitat von freimatz (Beitrag 1507301)

Zitat:

Zitat von fisipjm (Beitrag 1507264)

Zitat:

Zitat von freimatz (Beitrag 1507258)

Klarer ja, klar genug zweifelhaft.
Ich bin mir aber sicher dass für den Geschwindigkeitsnachteil das SQL schuld ist und nicht das TDictionary.

Nö, der SQL Server ist nicht Teil der Geschwindigkeitsmessung. Die beginnt erst nachdem die Daten schon abgeholt wurden.
Welche infos fehlen noch um an ein klar genug ran zu kommen?

Deine Aussage "Werfe ich jetzt in die SQL Abfrage noch ein 2. Feld rein dann wird aus der 1ms schon 50ms usw." lies mich zum Schluß kommen dass da was mit SQL dabei ist.
Wie die Kollegen hier auf FieldByName kommen erschließt sich mir nicht. Wenn denen das klar ist reicht das ja. Kompetentere wie z.B. Uwe und Stevie lassen sich eh nicht finden. ;-)

Ja, dass stimmt wohl :-D Die CodeRage Beiträge gestern waren wieder erste Sahne :-)
Ihr habt das Problem schon recht gut erkannt. Den Index Weg lassen ist natürlich am schnellsten, aber geht halt auf die "Bequemlichkeit".