-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
16. Dez 2015
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.
Make it work
Make it right
Make it fast (if you need it faster)
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
16. Dez 2015
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Dann wäre das Dictinary ja schneller als die Birnbaum-Listen? (die brauchten ja 4-30 Sekunden)
Kann doch gar nicht sein, so schlecht wie TDictionary implementiert ist :mrgreen:
(scheint aber wohl zu reichen)
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Die Formel ist relativ simpel:
Nimm 2 unterschiedliche Primzahlen
Die erste Primzahl ist dein PrimStartwert
Die zweite Primzahl ist dein PrimMultiplikator
Berehne den Hashwert mit
Hashwert = PrimStartwert;
Hashwert = Hashwert * PrimMultiplikator + HashwertVon( WertA )
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Und für alle Zweifler ein Testprogramm:
program Project1;
{$APPTYPE CONSOLE}
{$R *.res}
// ***
// *
// * Für Mäusekino einfach mal ausschalten
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Und das ist der Grund für die ganzen Kollisionen 420.000 Werte teilen sich 10.000 Hashwerte.
Nur das du eben einen Kollisionsautomaten verwendest :mrgreen:
Probier doch mal diesen Comparer
{ TGuidEqualityComparer }
function TGuidEqualityComparer.Equals(const Left, Right: TGuid): Boolean;
begin
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Warum war denn wohl mein erstes Fazit, dass der Hash-Algorithmus von stahli das Problem verursacht (zu langsam oder zu viele Kollisionen)? :roll:
Bei einer Entität ist die ID das ausschlaggebende Kriterium. Die ist gerne mal ein integer und wird fortlaufend (Datenbank) vergeben. Da wird es sogar egal, wo die Instanz im Speicher liegt, der Hashwert wird über die ID erzeugt.
Hier haben wir...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Wenn man etwas nicht nicht weiß, dann kann man die gute Tante fragen HashSet.
Und ein HashSet ist eine Menge von eindeutigen Werten.
Wenn die Implementierung so schlecht ist, was habe ich denn dann falsch gemacht wenn bei mir 1.000.000 Instanzen da in 179ms reinflutschen? :gruebel:
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
@stahli :thumb:
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Ja, merkt man dann, wenn man morgens schon Schaum vor dem Mund hat :stupid:
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Ein Dictionary ist keine sortierte Liste sondern eine HashSet mit einem Wert pro Schlüssel.
Genauso wie eine Waschmaschine kein Toaster ist, obwohl beide einen Stromanschluss haben, eine Öffnung um etwas hineinzustecken und einen Schalter zum einschalten.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
Fangen wir einmal von vorne an:
Ein Dictionary ist eine Key-Value-Menge
Für die Einsortierung braucht das Dictionary einen IEqualityComparer<TKey>
Dieser Comparer liefert für den Key eine Hash-Funktion und eine Gleichheits-Funktion
Wenn jetzt der Key von TObject abgleitet ist (also eine Klasse), dann geht der Standard-EqualityComparer auf die Methoden:
function TObject.Equals(...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
15. Dez 2015
var
lDict: TObjectDictionary<TObject, integer>;
lSw : TStopwatch;
begin
lDict := TObjectDictionary<TObject, integer>.Create( );
try
lSw := TStopwatch.StartNew;
while lDict.Count < 1000000 do
begin
lDict.Add( TObject.Create, 0 );
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
12. Okt 2015
Probier es doch einfach mit unterschiedliche Hash-Funktionen aus und teste dann mit einer vergleichbaren Beispielmenge, so wie das auch in deiner Anwendung zu erwarten wäre.
Dann bekommst du ein Gefühl dafür ...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
12. Okt 2015
Nun ja, du hast jetzt eine GetHashCode-Methode die wesentlich schneller als die Equals-Methode ist.
Nur wird diese GetHashCode-Methode immer nur einmal aufgerufen und die Equals-Methode für jeden Eintrag in dem Bucket.
Was ist denn jetzt wohl besser? Eben, GetHashCode sollte nicht langsam, aber auch nicht zu einfach sein und bei ähnlichen Werten sehr unterscheidliche Hash-Werte liefern. Im...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
12. Okt 2015
Nur dass es so eben langsam ist ... und wolltest du nicht gerade wegen schnell auf ein Dictionary umsteigen?
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
12. Okt 2015
"Theoretisch" ist es egal, was du als HashCode zurücklieferst, praktisch beeinflusst der HashCode die Such-Performance.
Bei der Suche nach einem Key wird der HashCode ermittelt und geschaut, ob es für diesen schon ein Töpfchen gibt (Bucket). Dann wird nur in diesem Töpchen weiter gesucht mit der Equals-Methode.
Lieferst du also immer den gleichen HashCode zurück, dann hast du nur einen Topf...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Sir Rufo,
11. Okt 2015
Um das Verhalten eines Typen als Key in einem Dictionary zu untersuchen, schaut man sich einfach die Ergebnisse vom zugehörigen IEqualityComparer an, den man durch Abfrage von TEqualityComparer<T>.Default bekommt.
procedure foo;
var
c: IEqualityComparer<TGuid>;
v1, v2: TGuid;
h1, h2: integer;
begin
c := TEqualityComparer<TGuid>.Default;
v1 := ...