Dictionary statt binärer Suche?

[idefix2]

Leider kann ich mit meinem Delphi 2009 auf dem Beispiel von Sir Rufo nicht aufsetzen, da gibt es anscheinend einiges noch nicht, was in dem Code verwendet wird.

Natürlich ist ein guter Algorithmus zum möglichst kollisionsfreien Berechnen der Hashcodes wichtig. Allerdings würde eine bessere Implementierung des Dictionary bei weitem nicht so empfindlich reagieren wie diese, wenn Kollisionen etwas häufiger vorkommen.

[Dejan Vu]

Zitat von Sir Rufo:

Achtung! Wenn bei einer Hashfunktion etwas mit xor auftaucht, ganz schnell zum nächsten Treffer gehen, denn das ist auch Murks

Echt? Viele Hash-Funktionen arbeiten damit: DEK, ELF, JS, MD5, PJW, SHA256 ...
ELF z.B. ist in UNIX sehr weit verbreitet, PJW wird im Compilerbau häufig verwendet, MD5 und SHA256 sind anerkannt..

[Mavarik]

Zitat von Sir Rufo:

Ergebnis auf meinem Rechner (Mittelwert von den 10 Durchläufen):

• ca. 28ms (mit MAENNER_HASH)
• ca. 7.972ms (ohne MAENNER_HASH)

PS Ich hätte den Test auch gerne mit 420.000 Einträgen gemacht, aber dann hätte ich die Ergebnisse für den originalen Hashcode heute wohl nicht mehr liefern können

Ich habe es dann spasseshalber mal mit 420.000 Einträgen gemacht...

• ca. 113.30ms (mit MAENNER_HASH)
• ca. 343093.80ms (ohne MAENNER_HASH)

Zum Vergleich mit 50.000 Einträgen

• ca. 11.40ms (mit MAENNER_HASH)
• ca. 3288.70ms (ohne MAENNER_HASH)

Mit MAENNER_HASH von 50.000->420.000 rechnerisch hätten 95.76 rauskommen "sollen"
Ohne MAENNER_HASH von 50.000->420.000 rechnerisch hätten nur 27625,08 rauskommen "sollen", ist aber faktor 12,4 langsammer...


Mavarik

[idefix2]

Das Ergebnis war genau so zu erwarten, weil der Algorithmus, mit dem Kollisionen durch diese Implementierung von TDirectory behandelt werden, zu immer grösseren "Klumpen" von Kollisionen führt, die die Performance komplett abstürzen lassen. Sobald sich einmal so ein Klumpen, aus welchem Grund immer, gebildet hat, hilft der beste Algorithmus zur gleichmässigen Verteilung der Hashkeys nicht mehr weiter, weil nicht zu vermeiden ist, dass immer wieder Hashkeys irgendwo in diesen Klumpen hineinfallen und ihn weiter vergrössern.
Und das ganze ist eine Teufelsspirale, weil je grösser ein Klumpen wird, umso grösser wird die Wahrscheinlichkeit, dass irgend ein zufälliger Hashkey gerade in diesen Klumpen hineinfällt.

[Sir Rufo]

Also halten wir mal fest:

Das von Emba implementierte TDictionary ist sehr performant, wenn man einen vernünftigen Hash-Algorithmus anbietet.

Hat man einen Grütze-Hash-Algorithmus, dann geht die Performance in den Keller.

Es gibt irgendwo auf dieser grossen weiten Welt jemand ganz kluges, der eine wesentlich bessere Implementierung von TDictionary bauen kann, der dann auch mit einem Grütze-Hash-Algorithmus besser klar kommt.

Die maximale Performance erhält man aber auch hier nur mit einem vernünftigen Hash-Algorithmus.

Mein Fazit:

1. Ich erstelle immer einen vernünftigen Hash-Algorithmus
2. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
3. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
4. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
5. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
6. Sollte das TDictionary zu langsam sein, dann suche ich nach einer Alternative, die messbar schneller ist als TDictionary

(Bis zum heutigen Tag bin ich immer nur bis zum Punkt 3. gekommen)

[einbeliebigername]

Hallo,

@Sir Rufo: Du hast mich überzeugt das wir in diesem Fall beide Recht haben.

Zitat von Sir Rufo:

Also halten wir mal fest:

Das von Emba implementierte TDictionary ist sehr performant, wenn man einen vernünftigen Hash-Algorithmus anbietet.

Falsch! Richtig: Die Implementierung von Emba ist performanter, wenn man einen vernünftigen Hash-Algorithmus anbietet.

Zitat von Sir Rufo:

Mein Fazit:

1. Ich erstelle immer einen vernünftigen Hash-Algorithmus
2. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
3. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
4. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
5. Sollte das TDictionary zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
6. Sollte das TDictionary zu langsam sein, dann suche ich nach einer Alternative, die messbar schneller ist als TDictionary

(Bis zum heutigen Tag bin ich immer nur bis zum Punkt 3. gekommen)

Wie oft bist du zu Punkt 3 gekommen? Wie viele andere Entwickler sind wie oft zu Punkt 3 gekommen? Währe es nicht besser wenn einmal jemand (Emba) Punkt 6 erledigt, und dann nur noch wenige ganz selten bis Punkt 3 müssen?

Denn den Hash-Algorithmus bei der Emba-Implementierung kannst du ja nicht im ganzen austauschen, da ein Teil fest in TDictionary eingebaut ist. Auch wird kein Programmierer von sich aus auf die Idee kommen für bis 32bit-Werte den Hash mittels einer Formel zu ermitteln. Da wird jeder einen Cast benutzen. Und dann schlägt der Feste Teil richtig böse zu.

einbeliebigername.

[stahli]

Das sehe ich auch so.
Es wäre halt einfacher, wenn man nur eine einfache "Id" als Integer übergeben müsste, die dann von der Komponente in einen passenden Hashwert umgerechnet wird.

Es würde Fehlermöglichkeiten halt auf einfache Weise reduzieren.

[Sir Rufo]

Um ehrlich zu sein komme ich zu 99% nicht über Punkt 1 hinaus.
Zu Punkt 3 komme ich eher nur in 0,01% aller Fälle.

Ob die TDictionary -Implementierung gut oder schlecht ist, ist mir so lange egal, wie die Performance ausreichend ist und das Dingen tut was es soll.

1. Make it work
2. Make it right
3. Make it fast (if you need it faster)

Und bislang war es halt schnell genug.

Ich bin aber offen für Alternativen ... dann pusten wir die gleichen Daten da mal rein und messen die Zeiten.

@stahli

Du kannst doch einfach eine Integer-ID zurückgeben (wenn diese ID die Entität eindeutig identifiziert). Du musst doch nur einen Hash zusammenrechnen, wenn du einen zusammengesetzte ID hast.

Und es gibt auch schon eine eingebaute Hash-Funktion BonJenkinsHash , der man einfach einen Pointer und Size auf die Daten gibt und der bastelt sich dann den Hashwert.

Ich sehe hier einfach keine Schwierigkeit beim Erstellen des Hash-Werts.

Man kann auch mal nach HashCodeBuilder suchen und sich dort das Konzept anschauen und in Delphi implementieren. Dann wird es eventuell einfacher.