Dictionary statt binärer Suche?

[stahli]

Ok, vielen Dank!

Hier wurde das auch schon mal behandelt: http://www.delphipraxis.net/184801-d...ictionary.html ("Compare" gibt es allerdings nicht zum überschreiben.)

Grundsätzlich funktioniert es jetzt.
Aber was mir noch nicht ganz klar ist, ist was ich als GetHashCode angeben soll.
Macht der Comparer nochmal etwas mit meinem Result oder muss ich selbst etwas Sinnvolles bereitstellen.
Mein fC ist ein globaler Zähler, der für jede neue Guid hochgezählt wird. Wird 10.000 erreicht, wird er wieder auf 0 gesetzt.
Ist das Dictionary so intelligent, dass es damit gut zurecht kommt?
Dann würde ich es dabei belassen.

Angenommen fC würde nur 3 mögliche Werte haben wäre es als HashCode ungeeignet, da das Dictionary dann nur 3 Gruppen als Vorsortierung für z.B. 1Mio Einträge hätte ... richtig?

Delphi-Quellcode:

  TGuidEqualityComparer = class(TEqualityComparer<TGuid>)
  public
    function Equals(const Left, Right: TGuid): Boolean; override;
    function GetHashCode(const Value: TGuid): Integer; override;
  end;

{ TGuidEqualityComparer }

function TGuidEqualityComparer.Equals(const Left, Right: TGuid): Boolean;
begin
  Result := (Left = Right);
end;

function TGuidEqualityComparer.GetHashCode(const Value: TGuid): Integer;
begin
  Result := Value.fC; // 0..99999
end;

...

var
  GC: IEqualityComparer<TGuid>;
begin
  GC := TGuidEqualityComparer.Create;
  fDict := TDictionary<TGuid, IsoGuid>.Create(GC);

[Sir Rufo]

"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 und die Suche dauert länger, als wenn du einen HashCode lieferst, der gut verteilt ist.

Nachtrag

Für einen zusammengesetzten HashCode bietet sich folgendes Verfahren an, wobei ein potenzieller Überlauf nicht schlimm, sondern bewusst genutzt wird:

Delphi-Quellcode:

hc := primeBase; // z.B. 17
hc := hc * primeMultiplikator // z.B. 397
  + hashPart;
...

Und ja, Basis und Multiplikator sollten Primzahlen sein.

[stahli]

Super, dann sollte alles passen.
Danke!

[Sir Rufo]

Zitat von stahli:

Super, dann sollte alles passen.
Danke!

Nur dass es so eben langsam ist ... und wolltest du nicht gerade wegen schnell auf ein Dictionary umsteigen?

[stahli]

Hmm, dann habe ich Dich falsch verstanden.

In meinem Fall gibt die Hashfunktion 0..99999 zurück.
Das wären doch dann bis 100000 Töpfe und wenige Kollisionen. -> https://de.wikipedia.org/wiki/Hashfunktion
Ist das nicht ok?
Nach meinem Gefühl wäre vielleicht ein div 10 oder div 100 sinnvoll, damit nicht so viele Töpfe angelegt werden!?

Was würde Deine Umrechnung bringen?

[Sir Rufo]

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 Idealfall bekommst du einen HashCode ohne Kollisionen und der Key wird mit einem Aufruf der Hash-Funktion und einem Aufruf der Vergleichs-Funktion gefunden oder eben nicht.

Dann wird es schnell.

Siehe dazu auch Hashfunktion - Kriterien für eine gute Hashfunktion
(wir brauchen aber Ordnung und kein Chaos -> also eine stabile Hash-Funktion)

Ein Gegenbeispiel für deine wenigen Töpfe:

Pack mal alle deine Sachen in Container (pro Farbe einen Container) und jetzt suche nach einer schwarzen Socke. Dauert wie lange?
Pack jetzt alle deine Sachen in Container (pro Farbe, Art, Größe, Hersteller, ... einen Container) und jetzt suche nach den schwarzen Wintersocken von Ergee. Dauert wie lange? Eben einfach zum passenden Container gehen und eins von den drei Paaren herausnehmen, fertig.

Genau so geht es dem Dictionary auch

[stahli]

Hmm, ich sehe nicht, warum meine jetzige Lösung dann langsam sein soll.
Ich nutze Integerwerte 0..99999, die relativ gleichmäßig verteilt sind.
Also sind nachher bis 100.000 Töpfe vorhanden, die irgendwann einige Einträge enthalten.

Als alternatives Kriterium könnte ich meinen zweiten Zeitstempel nehmen. Der ist weitestgehend eindeutig, sollte also i.d.R. nur einmal im Projekt vorliegen.
Jetzt könnte ich mir vorstellen, aus dem Zeitstempel einen Integerwert zu berechnen - aber was wäre da sinnvoll?

-> Z.B. fC * Succ(SekundenDesZeitstempels) ? Das würde einen größeren Wertebereich bringen.


Und ist es nicht so, dass das Dictionary die Bucket-Nr erst aus dem Integerwert berechnet (anhand der aktuellen Größe der Liste).
Dann ist also der Integerwert nicht direkt die Nr. des Buckets.


Echt peinlich solche Fragen.

[Sir Rufo]

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

[Dejan Vu]

Vielleicht als Anmerkungen:

1. Man muss sich keine großartigen Gedanken um eine Hashfunktion machen. Kann man, muss man aber nicht. Wenn die Daten einen eindeutigen Schlüssel haben (integer, string egal) reicht das. Man kann auch einen zusammengesetzten Schlüssel nehmen und string daraus basteln. Bei strings nehme ich eh den Elf-Hash, der ist bisher immer ausreichend gewesen. Hauptsache, der ursprüngliche Schlüssel identifiziert das Objekt eindeutig.
2. Wenn man einen reinen Integer-Dictionary nimmt, reicht es i.a. sich für die Größe der Tabelle eine Primzahl auszusuchen, um Kollisionen genügend zu vermeiden. Das sollte aber die Dictionary sowieso machen, weswegen es ausreicht, bei einem Integer-Key diesen Key selbst als Hashfunktion zu verwenden.
3. Eine gute Dictionary-Implementierung erkennt von alleine, wenn die Anzahl der Kollisionen zu hoch ist und vergrößert sich selbst.

Welche Hashfunktion man für eine UUID benutzen könnte, ist hier ganz gut beschrieben bzw. getestet.
http://programmers.stackexchange.com...ness-and-speed

[stahli]

@Sir Rufo
Also so völlig ohne Plan macht das m.E. keinen Sinn.

@Dejan Vu
Die Bilder sehen schön bunt aus.
Sehr viel mehr verstehe ich da leider nicht.
Bis sich das Gegenteil erweist vertraue ich einfach mal drauf, dass das Dict mit meinem Integer gut zurecht kommt...