Dictionary statt binärer Suche?

[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.
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 von stahli:

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.

[Dejan Vu]

Zitat von Sir Rufo:

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

[BUG]

Wieso Bob-Jenkins-hashst du nicht direkt alle Felder, sondern baust den Gesamthash so zusammen?
Ist das ein bekannteres Konstruktionsprinzip? (Edit: anscheinend ja ) 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 von 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.

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 TDictionary implementiert ist
(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.

[Mavarik]

Zitat von Sir Rufo:

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