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