Dictionary statt binärer Suche?

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

Zitat von stahli (Beitrag 1324564)

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:

Zitat von stahli (Beitrag 1324564)

Im Grund ähnlich den Pointern von Sir Rufo.

Nur das du eben einen Kollisionsautomaten verwendest :mrgreen:

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 :)

[stahli]

Ich habe das mal in mein Projekt eingebaut und komme so auf 3 Sekunden.

Ich ahne auch inzwischen, wo mein Denkfehler lag.
Ich dachte, ich übergebe in GetHashCode einen eindeutigen Integer oder Word-Wert und danach errechnet die Dictionary-Komponente daraus den "wirklichen" Hashwert für das korrekte Fach. M.E. war dieser auch abhängig von der Größe des Dictionarys.

Schließlich übergibt Sir Rufo ja auch nur einen Pointer, also quasi das Gleiche.
-> Natürlich habe ich aber GetHashCode überschrieben und damit die Funktionalität entsprechend geändert.

Wie man auf solch eine Formel kommt wird mir wohl immer rätselhaft bleiben. :stupid:
Aber ich will das jetzt auch nicht weiter ergründen.

Funktionsfähig ist es so zumindest. (Ich werde aus anderen Gründen wohl dennoch zunächst bei der Liste bleiben.)

Vielen Dank für die Geduld und Hilfe!

[Sir Rufo]

Die Formel ist relativ simpel:

1. Nimm 2 unterschiedliche Primzahlen
2. Die erste Primzahl ist dein PrimStartwert
3. Die zweite Primzahl ist dein PrimMultiplikator
4. Berehne den Hashwert mit
   
   Code:

   Hashwert = PrimStartwert;
   Hashwert = Hashwert * PrimMultiplikator + HashwertVon( WertA )
   HashWert = Hashwert * PrimMultiplikator + HashwertVon( WertB )
   ...

Fertig.

Diese Vorgehensweise kann man über Google zuhauf finden.

Achtung! Wenn bei einer Hashfunktion etwas mit xor auftaucht, ganz schnell zum nächsten Treffer gehen, denn das ist auch Murks ;)

Zitat:

Zitat von stahli (Beitrag 1324571)

Ich habe das mal in mein Projekt eingebaut und komme so auf 3 Sekunden

Wenn das immer noch so lange dauert, dann passt da bei dir immer noch etwas nicht.

[BUG]

Wieso Bob-Jenkins-hashst du nicht direkt alle Felder, sondern baust den Gesamthash so zusammen?
Ist das ein bekannteres Konstruktionsprinzip? (Edit: anscheinend ja :mrgreen:) Gibt es da eine ordentliche Quelle dazu?

[stahli]

Ok, ich akzeptiere die Formel mal so. :-)
Warum der Strom aus der Steckdose kleckert kann ich ja auch nicht bis ins Detail erklären.

Die 3 Sekunden werden schon weitestgehend zum Erzeugen der Objekte und füllen mit Daten benötigt, das Dict braucht somit nur einige Millisekunden.

[Sir Rufo]

Zitat:

Zitat von stahli (Beitrag 1324575)

Ok, ich akzeptiere die Formel mal so. :-)
Warum der Strom aus der Steckdose kleckert kann ich ja auch nicht bis ins Detail erklären.

Die 3 Sekunden werden schon weitestgehend zum Erzeugen der Objekte und füllen mit Daten benötigt, das Dict braucht somit nur einige Millisekunden.

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

Delphi-Quellcode:

TDictionary

implementiert ist :mrgreen:
(scheint aber wohl zu reichen)

[stahli]

Man muss es halt richtig machen, damit es funktioniert. :-)

Der Fehler lag dann darin, dass ich GetHashCode unzureichend überschrieben habe.
Vielleicht wäre es gut gewesen, eine Funktion "DefiniereIntegerwertFürHashcodeBerechnung" zu haben, die man überschreiben kann.
Aber wenn man weiß wie, dann geht es ja auch so. :-)

[idefix2]

Leider kann ich mit meinem Delphi 2009 auf dem Beispiel von Sir Rufo nicht aufsetzen, da gibt es anscheinend einiges noch nicht, was in dem Code verwendet wird.

Natürlich ist ein guter Algorithmus zum möglichst kollisionsfreien Berechnen der Hashcodes wichtig. Allerdings würde eine bessere Implementierung des Dictionary bei weitem nicht so empfindlich reagieren wie diese, wenn Kollisionen etwas häufiger vorkommen.

[Dejan Vu]

Zitat:

Zitat von Sir Rufo (Beitrag 1324572)

Achtung! Wenn bei einer Hashfunktion etwas mit xor auftaucht, ganz schnell zum nächsten Treffer gehen, denn das ist auch Murks ;)

Echt? Viele Hash-Funktionen arbeiten damit: DEK, ELF, JS, MD5, PJW, SHA256 ...
ELF z.B. ist in UNIX sehr weit verbreitet, PJW wird im Compilerbau häufig verwendet, MD5 und SHA256 sind anerkannt..

[Mavarik]

Zitat:

Zitat von Sir Rufo (Beitrag 1324569)

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 :)

Ich habe es dann spasseshalber mal mit 420.000 Einträgen gemacht...

• ca. 113.30ms (mit MAENNER_HASH)
• ca. 343093.80ms (ohne MAENNER_HASH)

Zum Vergleich mit 50.000 Einträgen

• ca. 11.40ms (mit MAENNER_HASH)
• ca. 3288.70ms (ohne MAENNER_HASH)

Mit MAENNER_HASH von 50.000->420.000 rechnerisch hätten 95.76 rauskommen "sollen"
Ohne MAENNER_HASH von 50.000->420.000 rechnerisch hätten nur 27625,08 rauskommen "sollen", ist aber faktor 12,4 langsammer...


Mavarik :stupid:

[idefix2]

Das Ergebnis war genau so zu erwarten, weil der Algorithmus, mit dem Kollisionen durch diese Implementierung von TDirectory behandelt werden, zu immer grösseren "Klumpen" von Kollisionen führt, die die Performance komplett abstürzen lassen. Sobald sich einmal so ein Klumpen, aus welchem Grund immer, gebildet hat, hilft der beste Algorithmus zur gleichmässigen Verteilung der Hashkeys nicht mehr weiter, weil nicht zu vermeiden ist, dass immer wieder Hashkeys irgendwo in diesen Klumpen hineinfallen und ihn weiter vergrössern.
Und das ganze ist eine Teufelsspirale, weil je grösser ein Klumpen wird, umso grösser wird die Wahrscheinlichkeit, dass irgend ein zufälliger Hashkey gerade in diesen Klumpen hineinfällt.

[Sir Rufo]

Also halten wir mal fest:

Das von Emba implementierte

Delphi-Quellcode:

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

Delphi-Quellcode:

TDictionary

bauen kann, der dann auch mit einem Grütze-Hash-Algorithmus besser klar kommt.

Die maximale Performance erhält man aber auch hier nur mit einem vernünftigen Hash-Algorithmus.

Mein Fazit:

1. Ich erstelle immer einen vernünftigen Hash-Algorithmus
2. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
3. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
4. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
5. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
6. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann suche ich nach einer Alternative, die messbar schneller ist als
   Delphi-Quellcode:

   TDictionary

(Bis zum heutigen Tag bin ich immer nur bis zum Punkt 3. gekommen)

[einbeliebigername]

Hallo,

@Sir Rufo: Du hast mich überzeugt das wir in diesem Fall beide Recht haben.

Zitat:

Zitat von Sir Rufo (Beitrag 1324604)

Also halten wir mal fest:

Das von Emba implementierte

Delphi-Quellcode:

TDictionary

ist sehr performant, wenn man einen vernünftigen Hash-Algorithmus anbietet.

Falsch! Richtig: Die Implementierung von Emba ist performanter, wenn man einen vernünftigen Hash-Algorithmus anbietet.

Zitat:

Zitat von Sir Rufo (Beitrag 1324604)

Mein Fazit:

1. Ich erstelle immer einen vernünftigen Hash-Algorithmus
2. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
3. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
4. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
5. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann schaue ich mir den Hash-Algorithmus nochmal an
6. Sollte das
   Delphi-Quellcode:

   TDictionary

   zu langsam sein, dann suche ich nach einer Alternative, die messbar schneller ist als
   Delphi-Quellcode:

   TDictionary

(Bis zum heutigen Tag bin ich immer nur bis zum Punkt 3. gekommen)

Wie oft bist du zu Punkt 3 gekommen? Wie viele andere Entwickler sind wie oft zu Punkt 3 gekommen? Währe es nicht besser wenn einmal jemand (Emba) Punkt 6 erledigt, und dann nur noch wenige ganz selten bis Punkt 3 müssen?

Denn den Hash-Algorithmus bei der Emba-Implementierung kannst du ja nicht im ganzen austauschen, da ein Teil fest in TDictionary eingebaut ist. Auch wird kein Programmierer von sich aus auf die Idee kommen für bis 32bit-Werte den Hash mittels einer Formel zu ermitteln. Da wird jeder einen Cast benutzen. Und dann schlägt der Feste Teil richtig böse zu.

einbeliebigername.

[stahli]

Das sehe ich auch so.
Es wäre halt einfacher, wenn man nur eine einfache "Id" als Integer übergeben müsste, die dann von der Komponente in einen passenden Hashwert umgerechnet wird.

Es würde Fehlermöglichkeiten halt auf einfache Weise reduzieren.

[Sir Rufo]

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

Delphi-Quellcode:

TDictionary

-Implementierung gut oder schlecht ist, ist mir so lange egal, wie die Performance ausreichend ist und das Dingen tut was es soll.

1. Make it work
2. Make it right
3. Make it fast (if you need it faster)

Und bislang war es halt schnell genug.

Ich bin aber offen für Alternativen ... dann pusten wir die gleichen Daten da mal rein und messen die Zeiten.

@stahli

Du kannst doch einfach eine Integer-ID zurückgeben (wenn diese ID die Entität eindeutig identifiziert). Du musst doch nur einen Hash zusammenrechnen, wenn du einen zusammengesetzte ID hast.

Und es gibt auch schon eine eingebaute Hash-Funktion

Delphi-Quellcode:

BonJenkinsHash

, der man einfach einen Pointer und Size auf die Daten gibt und der bastelt sich dann den Hashwert.

Ich sehe hier einfach keine Schwierigkeit beim Erstellen des Hash-Werts.

Man kann auch mal nach HashCodeBuilder suchen und sich dort das Konzept anschauen und in Delphi implementieren. Dann wird es eventuell einfacher.