AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Dictionary statt binärer Suche?

Ein Thema von stahli · begonnen am 7. Aug 2015 · letzter Beitrag vom 16. Dez 2015
 
einbeliebigername

Registriert seit: 24. Aug 2004
140 Beiträge
 
Delphi XE8 Professional
 
#29

AW: Dictionary statt binärer Suche?

  Alt 15. Dez 2015, 14:46
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.

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.

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.

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.
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:12 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz