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
Antwort Antwort
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.358 Beiträge
 
Delphi 11 Alexandria
 
#1

AW: Dictionary statt binärer Suche?

  Alt 11. Okt 2015, 19:54
Jetzt habe ich das Problem teilweise schon wieder.
Mal ein paar Auszüge:

Delphi-Quellcode:
  TGuid = record // eigene GUID
  private
    fTS1: TDateTime;
    fTS2: TDateTime;
    fC: LongWord;
    function get_AsString: String;
    function get_TS1: TDateTime;
    function get_TS2: TDateTime;
    procedure set_AsString(const Value: String);
    function get_C: LongWord;
  public
    class operator Equal(const Guid1, Guid2: TGuid): Boolean;
    class operator NotEqual(const Guid1, Guid2: TGuid): Boolean;
    class operator GreaterThan(Guid1, Guid2: TGuid): Boolean;
    // class operator GreaterThanOrEqual(Guid1, Guid2: TsoGuid): Boolean;
    class operator LessThan(Guid1, Guid2: TGuid): Boolean;
    // class operator LessThanOrEqual(Guid1, Guid2: TsoGuid): Boolean;
    function IsNotEmpty: Boolean;
    function IsEmpty: 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;
    property AsString: String read get_AsString write set_AsString;
  end;

...

class operator TGuid.Equal(const Guid1, Guid2: TGuid): Boolean;
begin
  Result := (Guid1.fTS1 = Guid2.fTS1) and (Guid1.fTS2 = Guid2.fTS2) and (Guid1.fC = Guid2.fC);
end;

...

      aGuid.AsString := aId;

      if Pos('-00002', aGuid.AsString) > 0 then // TEST, diese GUID ist definitiv enthalten
      begin
        System.SysUtils.Beep;
        CodeSite.Send('Get:' + aGuid.AsString + ' (from ' + IntToStr(Project.DataGuidList.Count) + ')');
        for Key in Project.DataGuidList.Keys do
        begin
          if (aGuid = Key) then // der Key ist mit der gesuchten Guid identisch
          begin
            CodeSite.Send('Found! ' + aGuid.AsString);
            S1 := Key.AsString;
            Value := nil;
            Project.DataGuidList.TryGetValue(Key, Value);
            if Assigned(Value) then
              S2 := Value.Guid.AsString
            else
              S2 := 'nil';
            CodeSite.Send(S1 + ': ' + S2); // Key wird gefunden
            S1 := aGuid.AsString;
            Value := nil;
            Project.DataGuidList.TryGetValue(aGuid, Value);
            if Assigned(Value) then
              S2 := Value.Guid.AsString
            else
              S2 := 'nil';
            CodeSite.Send(S1 + ': ' + S2); // aGuid wird nicht gefunden obwohl dieses identisch zu Key ist !?
            S1 := Key.AsString;
            Value := nil;
            Project.DataGuidList.TryGetValue(Key, Value);
            if Assigned(Value) then
              S2 := Value.Guid.AsString
            else
              S2 := 'nil';
            CodeSite.Send(S1 + ': ' + S2); // Key wird gefunden
            aGuid := Key; // aGuid wird Key zugewiesen, obwohl ich sonst keine Differenz feststellen kann
            S1 := aGuid.AsString;
            Value := nil;
            Project.DataGuidList.TryGetValue(aGuid, Value);
            if Assigned(Value) then
              S2 := Value.Guid.AsString
            else
              S2 := 'nil';
            CodeSite.Send(S1 + ': ' + S2); // aGuid wird jetzt gefunden
          end;
          S1 := Key.AsString;
          Value := nil;
          Project.DataGuidList.TryGetValue(Key, Value);
          if Assigned(Value) then
            S2 := Value.Guid.AsString
          else
            S2 := 'nil';
          CodeSite.Send(S1 + ': ' + S2); // Key wird gefunden
        end;
        if not Project.DataGuidList.TryGetValue(aGuid, lGuid) then
          System.SysUtils.Beep;
      end;

{ Log
Found! 20151011203151087-20151011203151630-00002
20151011203151087-20151011203151630-00002: 20151011203151087-20151011203151630-00002
20151011203151087-20151011203151630-00002: nil
20151011203151087-20151011203151630-00002: 20151011203151087-20151011203151630-00002
20151011203151087-20151011203151630-00002: 20151011203151087-20151011203151630-00002
20151011203151087-20151011203151630-00002: 20151011203151087-20151011203151630-00002
}
Hat jemand eine Idee, woran das liegen kann?
Der Equal-Operator liefert True zurück. Ich finde zwischen aGuid und Key keinen Unterschied.
Warum findet das Dictionary nur Einträge mit Key als Suchkriterium?
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)

Geändert von stahli (11. Okt 2015 um 21:33 Uhr) Grund: Oups, hatte den Code nochmal ersetzt und die Kommentare gelöscht. :-(
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#2

AW: Dictionary statt binärer Suche?

  Alt 11. Okt 2015, 21:33
Um das Verhalten eines Typen als Key in einem Dictionary zu untersuchen, schaut man sich einfach die Ergebnisse vom zugehörigen Delphi-Referenz durchsuchenIEqualityComparer an, den man durch Abfrage von TEqualityComparer<T>.Default bekommt.
Delphi-Quellcode:
procedure foo;
var
  c: IEqualityComparer<TGuid>;
  v1, v2: TGuid;
  h1, h2: integer;
begin
  c := TEqualityComparer<TGuid>.Default;
  v1 := ...
  v2 := ...
  Assert( v1=v2 ); // gleiche Werte
  h1 := c.GetHashCode( v1 );
  h2 := c.GetHashCode( v2 );
  Assert( h1=h2 ); // sollten den gleichen Hashcode haben
  Assert( c.Equals( v1, v2 ); // und als gleich erkannt werden
end;
Wenn hier jetzt ein Fehler kommt, dann weiß man, warum das mit dem Dictionary nicht funktioniert.

Dann muss man sich auf die Suche machen oder einen eigenen IEqualityComparer<TGuid> mitliefern.
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.358 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: Dictionary statt binärer Suche?

  Alt 12. Okt 2015, 18:46
Ok, vielen Dank!

Hier wurde das auch schon mal behandelt: http://www.delphipraxis.net/184801-d...ictionary.html ("Compare" gibt es allerdings nicht zum überschreiben.)

Grundsätzlich funktioniert es jetzt.
Aber was mir noch nicht ganz klar ist, ist was ich als GetHashCode angeben soll.
Macht der Comparer nochmal etwas mit meinem Result oder muss ich selbst etwas Sinnvolles bereitstellen.
Mein fC ist ein globaler Zähler, der für jede neue Guid hochgezählt wird. Wird 10.000 erreicht, wird er wieder auf 0 gesetzt.
Ist das Dictionary so intelligent, dass es damit gut zurecht kommt?
Dann würde ich es dabei belassen.

Angenommen fC würde nur 3 mögliche Werte haben wäre es als HashCode ungeeignet, da das Dictionary dann nur 3 Gruppen als Vorsortierung für z.B. 1Mio Einträge hätte ... richtig?


Delphi-Quellcode:
  TGuidEqualityComparer = class(TEqualityComparer<TGuid>)
  public
    function Equals(const Left, Right: TGuid): Boolean; override;
    function GetHashCode(const Value: TGuid): Integer; override;
  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; // 0..99999
end;

...

var
  GC: IEqualityComparer<TGuid>;
begin
  GC := TGuidEqualityComparer.Create;
  fDict := TDictionary<TGuid, IsoGuid>.Create(GC);
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#4

AW: Dictionary statt binärer Suche?

  Alt 12. Okt 2015, 19:50
"Theoretisch" ist es egal, was du als HashCode zurücklieferst, praktisch beeinflusst der HashCode die Such-Performance.

Bei der Suche nach einem Key wird der HashCode ermittelt und geschaut, ob es für diesen schon ein Töpfchen gibt (Bucket). Dann wird nur in diesem Töpchen weiter gesucht mit der Equals-Methode.

Lieferst du also immer den gleichen HashCode zurück, dann hast du nur einen Topf und die Suche dauert länger, als wenn du einen HashCode lieferst, der gut verteilt ist.

Nachtrag

Für einen zusammengesetzten HashCode bietet sich folgendes Verfahren an, wobei ein potenzieller Überlauf nicht schlimm, sondern bewusst genutzt wird:
Delphi-Quellcode:
hc := primeBase; // z.B. 17
hc := hc * primeMultiplikator // z.B. 397
  + hashPart;
...
Und ja, Basis und Multiplikator sollten Primzahlen sein.
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)

Geändert von Sir Rufo (12. Okt 2015 um 20:07 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.358 Beiträge
 
Delphi 11 Alexandria
 
#5

AW: Dictionary statt binärer Suche?

  Alt 12. Okt 2015, 20:00
Super, dann sollte alles passen.
Danke!
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#6

AW: Dictionary statt binärer Suche?

  Alt 12. Okt 2015, 20:09
Super, dann sollte alles passen.
Danke!
Nur dass es so eben langsam ist ... und wolltest du nicht gerade wegen schnell auf ein Dictionary umsteigen?
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.358 Beiträge
 
Delphi 11 Alexandria
 
#7

AW: Dictionary statt binärer Suche?

  Alt 12. Okt 2015, 20:26
Hmm, dann habe ich Dich falsch verstanden.

In meinem Fall gibt die Hashfunktion 0..99999 zurück.
Das wären doch dann bis 100000 Töpfe und wenige Kollisionen. -> https://de.wikipedia.org/wiki/Hashfunktion
Ist das nicht ok?
Nach meinem Gefühl wäre vielleicht ein div 10 oder div 100 sinnvoll, damit nicht so viele Töpfe angelegt werden!?

Was würde Deine Umrechnung bringen?
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Antwort Antwort


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 06:05 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