Performancefrage für ein einfaches Matching

[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)

[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 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

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.