Dictionary statt binärer Suche?

[Mavarik]

Zitat von idefix2:

Key ist das TObject, Value ist der integer? Sollte es nicht andersrum sein?

Der Value ist doch egal für die Sortierung. Mit dem TObject als Key hat "er" dadurck immer einen Pointer der sortiert werden muss...

[Sir Rufo]

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:

Delphi-Quellcode:

function TObject.Equals( Obj:TObject ) : Boolean; virtual;
function TObject.GetHashCode() : Integer; virtual;

Wenn TObject.GetHashCode nicht überschrieben wurde, dann wird dort der Referenz-Zeiger als Integer-Wert zurückgeliefert (bei x64 etwas anders).

Somit haben wir dort garantiert keine Kollisionen.

Das wollte ich damit nur zeigen. Keine Kollisionen -> Dictionary ganz schnell.
Wird das Dictionary langsam, dann hat man Mukrs beim HashCode gebaut.

Und TDictionary<TObject,Integer> ist absolut bewusst, da ich das Dictionary hier als ein HashSet missbrauche.

[bernau]

Zitat von Sir Rufo:

Und TDictionary<TObject,Integer> ist absolut bewusst, da ich das Dictionary hier als ein HashSet missbrauche.

Aber ist es nicht so, das der TE anhand der GUID das Interface/Object geliefert haben möchte? Dann sollte doch die GUID im KEY stehen und nicht das Interface/Object.

[stahli]

Der Sir wollte nur zeigen, dass die Anzahl der Einträge letztlich kein Problem darstellt, was ich nun auch einsehe.

Offenbar muss man aber für die Berechnung des Hashwertes eine optimale Lösung finden, was mir vorliegend nicht gelungen ist.

Deshalb hat sich mein Dic nicht performant genug verhalten.

Aber ich habe mit der einfachen sortierten Liste eine für mich sehr gut passende Alternative, mit der ich sehr gut zurecht komme.

[Sir Rufo]

@stahli

[einbeliebigername]

Hallo,

es lässt mir keine Ruhe, ich muss auch mal was dazu sagen. Erstmal die Frage ob sich jemand die Implementierung von TDictionary<TKey,TValue> angeschaut hat? Denn ich glaube die Implementierung ist das Problem.

Zitat von Sir Rufo:

Ein Dictionary ist keine sortierte Liste sondern eine HashSet mit einem Wert pro Schlüssel.

Was ist denn ein HashSet? Ich kenne nur den Begriff Hashtabelle, welche sich nach meinem Kenntnisstand (und da lasse ich mich gern eines Besseren belehren) kollisionsfest auf zwei Arten implementieren lassen:

Delphi-Quellcode:

// Hash-Wert ist der 1.Index im zweidimensionalen Array
THashTable= array of array of record
  Key: TKey;
  Value: TValue;
end;

oder

Delphi-Quellcode:

THashTable= array of record
  Hash: THash; // Array ist nach Hash sortiert, Zugriff mittels binärer Suche nach dem Hash
  Values: array of record
    Key: TKey;
    Value: TValue;
  end;
end;

Folgende Aussagen meinerseits beziehen sich auf die Implementierung vom TDictionary<TKey,TValue> im Delphi-XE8.

Leider wird keine der Varianten benutzt. Die Implementierung ist sicherlich Creative. Ob sie auch Klever ist, wage ich zu bezweifeln.

Zitat von Mavarik:

Der Value ist doch egal für die Sortierung. Mit dem TObject als Key hat "er" dadurck immer einen Pointer der sortiert werden muss...

Im Dictionary wird gar nicht sortiert. Jedenfalls kann ich das Sortierkriterium nicht erkennen.

Zitat von Sir Rufo:

Wenn TObject.GetHashCode nicht überschrieben wurde, dann wird dort der Referenz-Zeiger als Integer-Wert zurückgeliefert (bei x64 etwas anders).

Somit haben wir dort garantiert keine Kollisionen.

Im x64 haben wir wohl Kollisionen, da der Hashwert 32 Bit hat und die Pointer 64 Bit haben. Und dann ist im Dictionary der Dreh- und Angelpunkt die Funktion:

Delphi-Quellcode:

function TDictionary<TKey,TValue>.GetBucketIndex(const Key: TKey; HashCode: Integer): Integer;
var
  start, hc: Integer;
begin
  if Length(FItems) = 0 then
    Exit(not High(Integer));

  start := HashCode and (Length(FItems) - 1);
  Result := start;
  while True do
  begin
    hc := FItems[Result].HashCode;

    // Not found: return complement of insertion point.
    if hc = EMPTY_HASH then
      Exit(not Result);

    // Found: return location.
    if (hc = HashCode) and FComparer.Equals(FItems[Result].Key, Key) then
      Exit(Result);

    Inc(Result);
    if Result >= Length(FItems) then
      Result := 0;
  end;
end;

Für mich ist bei diesem Algorithmus der ermittelte Startindex der eigentliche Hash, denn wenn an der Stelle das Gesuchte nicht liegt, wird anschließend eine sequenzielle Suche durchgeführt, was man wegen teuer ja nicht will. Und bei meinen Versuchen mit TObjectDictionary<TObject,Integer> bekommen sehr viele Objekte den gleichen Startindex.

Und wenn man sich dann noch Grow und vor allem Rehash anschaut sieht man auch wieso Stahli das misst was er misst.

Also immer schön überprüfen ob die eingesetzten Klassen auch das leisten, weswegen man sie einsetzt.

einbeliebigername.

[stahli]

Bei Video2Brain ist ein interessantes Tutorial zu Datenstrukturen und darin auch zu Hash-basierten Strukturen.
https://www.video2brain.com/de/video...atenstrukturen
Ist halt leider kostenpflichtig.

Das ist recht einfach gehalten und daher gut verständlich.

Was Emba im Detail umgesetzt hat kann ich nicht wirklich nachvollziehen.
Insbesondere erschließt sich mir nicht, was ich beachten müsste, um effektive Hashwerte zu erhalten.

Aber wie gesagt. Ich komme derzeit auch sehr gut ohne aus.

PS: Ich meine mich zu erinnern, dass AQTime genau auch Grow und Rehash als Bremse ausgemacht hatte. Und ich hatte daraus dann interpretiert, dass ich das dann nicht ändern kann, weil das ja ein Verhalten der Komponente ist.

[idefix2]

Wenn ein Objekt als Key zum Sortieren übergeben wird, dann sollte doch normalerweise nach dem Inhalt des Objekts (den es nicht gibt) sortiert werden und nicht nach dem Pointer, oder sehe ich das falsch?

edit:
Ok, ich war schneller als Sir Rufo mir seiner Antwort, bzw. hat sich das überschnitten. Wenn gethashcode vom TObject den Referenz-Zeiger liefert, ist alles klar, dann funktioniert das. Ist allerdings etwas verwirrend.

[Sir Rufo]

Zitat von idefix2:

Wenn ein Objekt als Key zum Sortieren übergeben wird, dann sollte doch normalerweise nach dem Inhalt des Objekts (den es nicht gibt) sortiert werden und nicht nach dem Pointer, oder sehe ich das falsch?

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.