Dictionary statt binärer Suche?

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

[Sir Rufo]

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?

[einbeliebigername]

Zitat von Sir Rufo:

Wenn die Implementierung so schlecht ist, was habe ich denn dann falsch gemacht wenn bei mir 1.000.000 Instanzen da in 179ms reinflutschen?

Du vergleichst Äpfel mit Birnen. Deine Pointer werden durch ein Cast in die Hash-Werte gewandelt. Stahli's Guids sind aber 128 Bit breit und da muss schon gerechnet werden um die Hash-Werte zu bekommen. Und dann ist bei solchen Algorithmen leider nicht nur die Anzahl der Elemente, sonder auch ihre Verteilung und Reinfolge ausschlaggebend. [nur dahingesagt]Ist schon ein Unterschied ob man die Schlüsselmenge [1, 2, 3, 4, ...] oder [4, 8, 12, 16, ...] hat, auch wenn beide 1.000.000 Elemente haben.[/nur dahingesagt]

@idefix2: +100

einbeliebigername.

[Sir Rufo]

Warum war denn wohl mein erstes Fazit, dass der Hash-Algorithmus von stahli das Problem verursacht (zu langsam oder zu viele Kollisionen)?

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 eine GUID. Na und, dann eben den Hashwert davon bilden. Aber mit Sinn und Verstand. Und wenn das Erzeugen zu lange dauert, dann einfach mit einem Cache des Wertes (muss ja eh ein stabiler Hashwert sein).

[stahli]

Ok, sofern weitere Details interessant sind will ich mal ein wenig die Hosen runter lassen.

Delphi-Quellcode:

  TGuid = record
  private
    ...
  public
    ...
    class operator Equal(const Guid1, Guid2: TGuid): Boolean;
    ...
    property TS1: TDateTime read get_TS1 write fTS1;
    property TS2: TDateTime read get_TS2 write fTS2;
    property C: LongWord read get_C write fC;
  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;
end;

...

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

...


Dic.TryGetValue(aGuid, rGuid);
Dic.Remove(aGuid);
Dic.Add(aGuid, aGuidIntf);

Somit wird also m.E. der Longword-Bestandteil (möglicher Wertebereich 0..99999) der GUID als Hash-Basis verwendet.
Im Grund ähnlich den Pointern von Sir Rufo.

Wie gesagt, für mich nicht wichtig, aber falls Ihr weiter diskutieren wollt...

[Dejan Vu]

Na ja, und diese Werte sind vermutlich nicht ganz so unterschiedlich, wie man das gerne hätte. Hier im Forum , gibt's doch diverse alternative Implementierungen, die brauchbar sind, oder nicht? Da muss man nicht schauen, wie Emba das macht.

Die Hashfunktion überführt den Schlüssel in einen Wertebereich, der in die interne Implementierung der Dictionary passt: Meist ist das ein Array[X], wobei X i.a. eine Primzahl ist.
Wenn das Array 'voll' ist (mehr oder minder), dann wird das Array vergrößert (auf z.B. Y)und alle Hashwerte neu berechnet. Dieses mal werden die Hashwerte aber auf den größeren Wertebereich gemappt.
Dabei kann das Umschlüsseln durchaus langsam sein (relativ zu einem einfach insert), aber im Durchschnitt ist die Einfügeoperation dennoch sehr schnell. Wieso? Man muss sich nur mal überlegen, was alles passiert:
1x Hash berechnen und auf Wertebereich Mappen (mit Modulo). Das ist der Index in das Array.
Wenn Array [Index]=Frei, dann Value dort reinpacken und fertig.
Sonst ist im Array z.B. eine Liste. Wenn man hier eine verkettete Liste nähme, müsste man den neuen Wert nur in die Liste einhängen. Auch sehr schnell.

Also nochmal: 1x Hash berechnen, 1x Modulo. Fertig.
Nur wenn die Liste voll wird (oder die Hashfunktion Müll, hallo Sir Rufo), muss man den minimalen Overhead für das Einhängen in die Liste einberechnen.

Aber selbst ein Hash über einen String ist da noch sauschnell.

[Sir Rufo]

Zitat von stahli:

Somit wird also m.E. der Longword-Bestandteil (möglicher Wertebereich 0..99999) der GUID als Hash-Basis verwendet.

Und das ist der Grund für die ganzen Kollisionen 420.000 Werte teilen sich 10.000 Hashwerte.

Zitat von stahli:

Im Grund ähnlich den Pointern von Sir Rufo.

Nur das du eben einen Kollisionsautomaten verwendest

Probier doch mal diesen Comparer

Delphi-Quellcode:

{ TGuidEqualityComparer }

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

function TGuidEqualityComparer.GetHashCode(const Value: TGuid): Integer;
begin
  Result := 17;
  Result := Result * 397 + FC;
  Result := Result * 397 + BobJenkinsHash( FTS1, sizeOf( TDateTime ), 5 );
  Result := Result * 397 + BobJenkinsHash( FTS2, sizeOf( TDateTime ), 7 );
end;

und du wirst Pipi in die Augen bekommen

[Sir Rufo]

Und für alle Zweifler ein Testprogramm:

Delphi-Quellcode:

program Project1;

{$APPTYPE CONSOLE}
{$R *.res}

// ***
// *
// * Für Mäusekino einfach mal ausschalten
// *
{$DEFINE MAENNER_HASH}
// *
// ***

uses
  System.Diagnostics,
  System.Generics.Collections,
  System.Generics.Defaults,
  System.SysUtils;

type
  TGuid = record
  private
    FTS1: TDateTime;
    FTS2: TDateTime;
    FC  : LongWord;
  public
    class operator Equal( const L, R: TGuid ): Boolean;

    function GetHashCode( ): Integer;

    property TS1: TDateTime read FTS1 write FTS1;
    property TS2: TDateTime read FTS2 write FTS2;
    property C: LongWord read FC write FC;
  end;

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

  { TGuid }

class operator TGuid.Equal( const L, R: TGuid ): Boolean;
begin
  Result := ( L.TS1 = R.TS1 ) and ( L.TS2 = R.TS2 ) and ( L.C = R.C );
end;

function TGuid.GetHashCode: Integer;
begin
{$IFDEF MAENNER_HASH}
  Result := 17;
  Result := Result * 397 + FC;
  Result := Result * 397 + BobJenkinsHash( FTS1, sizeOf( TDateTime ), 5 );
  Result := Result * 397 + BobJenkinsHash( FTS2, sizeOf( TDateTime ), 7 );
{$ELSE}
  Result := FC;
{$ENDIF}
end;

{ TGuidOrgEqualityComparer }

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

function TGuidOrgEqualityComparer.GetHashCode( const Value: TGuid ): Integer;
begin
  Result := Value.GetHashCode;
end;

procedure Test;
var
  lCount: Integer;
  lDict : TDictionary<TGuid, Integer>;
  lsw   : TStopWatch;
  lTS1  : TDateTime;
  lGuid : TGuid;
begin
  lsw := TStopWatch.Create;

  lCount := 0;

  while lCount < 10 do
    begin

      lDict := TDictionary<TGuid, Integer>.Create( TGuidOrgEqualityComparer.Create );
      try
        lsw.Start;

        lTS1 := Now;

        while lDict.Count < 50000 do
          begin
            lGuid.TS1 := lTS1;
            lGuid.TS2 := Random * 2000;
            lGuid.C   := Random( 10000 );

            lDict.Add( lGuid, 0 );

            if lDict.Count mod 1000 = 0
            then
              write( '.' );
          end;
          Writeln;

        lsw.Stop;
      finally
        lDict.Free;
      end;

      inc( lCount );

    end;

  Writeln( 'Schnitt: ', ( lsw.ElapsedMilliseconds / lCount ):0:2, 'ms' );

end;

begin
  Randomize;
  try
    Test;
  except
    on E: Exception do
      Writeln( E.ClassName, ': ', E.Message );
  end;
  ReadLn;

end.

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

[idefix2]

Diese Implementierung ist allerdings ziemlich miserabel.
Für eine brauchbare Hashtabelle braucht man entweder ein zweidimensionales Feld, oder eine Familie von Hashfunktionen, durch die man sicherstellt, dass keine "Ballungen" von Kollisionen auftreten.

Wenn ein eindimensionales Hashfeld verwendet und bei einer Kollision einfach immer der nächsthöhere Index genommen wird, entstehen immer grössere Blöcke von bereits besetzten Indizes, und wenn ein neuer Hashwert irgendwo in so einen Block hineinfällt, vergrössert sich der besetzte Block weiter und damit 1. die Wahrscheinlichkeit, dass irgend ein Hashwert wieder in diesen Block fällt und ihn weiter verlängert, und 2. natürlich die durchschnittliche Suchzeit nach jedem Schlüssel, dessen Hashberechnung irgendwo in diesem besetzten Block aufschlägt.

@ Sir Rufo
Die Verwendung von der Reihe nach angelegten Speicheradressen als Index ist eine absolut atypische Anwendung. Nachdem ein TObject eine Anzahl n Bytes braucht und das nächste TObject typischerweise die Adresse des vorigen TObject + n erhält, wird hier die Problematik der Kollisionsballungen automatisch entschärft. Bei zufälligen Werten für den Index hast du in aller Regel keine so optimal-gleichmässige Verteilung der Schlüsselwerte (die durch das "and" bei der Erzeugung des Hashindex eine optimal-gleichmässige Verteilung der Hashwerte über die ganze Breite der Hashtabelle ergibt).