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
Seite 1 von 6  1 23     Letzte »    
Benutzerbild von stahli
stahli

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

Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 13:09
Ich halte Interfaces, die eine GUID haben, in einer Liste.

Mit Hilfe binärer Suche werden die Interfaces anhand der GUID sortiert eingefügt und wieder herausgesucht.

Das funktioniert schnell und gut.


Jetzt wollte ich testen, ob es mit einem Dictionary noch schneller ginge.
Irgendwas mache ich offenbar falsch.
Count erhöht sich nach einem Add. Aber der Eintrag wird dann nicht gefunden.

Das Ganze sieht etwa so aus:

Delphi-Quellcode:
  IMyInf = Interface
    property Guid: TGuid ...
    ...
  end;

  aGuid := MyIntf.Guid;
  MyDict.Add(aGuid, MyIntf);

  MyDict.TryGetValue(aGuid, MyIntf); // MyIntf ist immer nil
Die GUID´s sind in Ordnung und stimmen überein.
Gestern Abend konnte ich nicht weiter suchen.
Kann sein, dass ich einen anderen Fehler im Projekt habe, aber eigentlich sollte es dort so sein, wie hier zusammengefasst.
Oder ist mein Ansatz falsch?

Und macht es in meinem Beispiel überhaupt Sinn, von binärer Suche auf ein Dictionary umzustellen? Es können ein paar tausend bis zu einigen Mio Interfaces verwaltet werden.

Und was genau gibt Capacity im Constructor an (ich habe dazu keine klare Aussage in der Hilfe gefunden). Ich kenne es so, dass diese die Anzahl der Cluster angibt, auf die die Einträge aufgeteilt werden.
Scheinbar wird diese dann dynamisch erhöht. Stimmt das? Wie soll das funktionieren, dass dann noch Einträge wiedergefunden werden?
Emba setzt da in der Hilfe wohl zu viele Vorkenntnisse voraus. Jedenfalls kann ich da einiges nicht richtig einordnen.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Der schöne Günther

Registriert seit: 6. Mär 2013
6.159 Beiträge
 
Delphi 10 Seattle Enterprise
 
#2

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 13:27
Das was du bei einem TDictionary<> im Konstruktor angibst ist die "Startkapazität"- Also auf wie viele Einträge das Dictionary vorbereitet ist bevor es komplett umstrukturieren muss. Bei Containern wie der TList<> ist das gleich: Intern legt er es in einem Array ab. Wenn das Array zu voll wird, reserviert er sich den doppelten Platz davon, kopiert den alten Inhalt in das neue Array und gibt das alte frei. Beim Dictionary ähnlich, nur dass es (ohne zu messen) wohl um einiges zeitaufwändiger ist.

Siehe auch: TDictionary<>.TrimExcess()

Wenn du also die maximale Größe im Voraus weißt kann das einiges an Zeit sparen.



PS: Ich weiß nicht was du genau machst, aber wenn du dem Dictionary etwas hinzugefügt hast bekommst du es auch mit TryGetValue wieder heraus.

Geändert von Der schöne Günther ( 7. Aug 2015 um 13:33 Uhr)
  Mit Zitat antworten Zitat
TiGü

Registriert seit: 6. Apr 2011
Ort: Berlin
3.070 Beiträge
 
Delphi 10.4 Sydney
 
#3

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 13:46
Wie immer empfiehlt sich auch hier das Programmieren einer ganz kleinen Konsolenanwendung, um den Fehler im Vergleich zum richtigen Programm zu finden.
Auch lässt sich der Inhalt des Dictonary im Debugger und ggf. im Watch-Fenster anschauen.
Ist es gefüllt nach dem Add?
Ist es immer noch gefüllt vor dem TryGetValue?
Sicher das du die gleiche Dictonary-Instanz verwendest?
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 13:57
@Schönling
Ok, wenn das Dict. kopiert und die Hashwerte neu berechnet werden, dann ist das nachvollziehbar. Das wird dann sicher etwas dauern.

@TiGü
Ok, dann scheint mein Ansatz erst mal nicht völlig falsch zu sein, was evtl. auch möglich gewesen wäre.
Ich hatte in der Nacht dann keine Neven mehr, das Problem noch weiter zu zerlegen.

Ich denke inzwischen, für meinen Fall ist die binäre Suche vermutlich der bessere Weg. Ich kann vorher nicht sagen, wie viele Einträge verwaltet werden müssen.
Ich teste das mal am WE noch etwas aus...
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#5

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 14:07
Das mit dem Vergrößern eines Dictionary kann man vernachlässigen (sofern die Größe immer verdoppelt wird). Das kommt dann bei 2 Milliarden Add-Aufrufen insgesamt ca. 25-32 mal vor (je nach Anfangsgröße und Strategie).

Das eine mal, wo dann vergrößert wird, dauert es vielleicht ein paar MS, aber das war es dann auch. Ansonsten ist eine Dictionary auch mit 2 Mrd Einträgen genauso schnell wie mit 200. Bei einer binären Suche ist das nicht so.
  Mit Zitat antworten Zitat
TiGü

Registriert seit: 6. Apr 2011
Ort: Berlin
3.070 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 15:09
Ich denke inzwischen, für meinen Fall ist die binäre Suche vermutlich der bessere Weg. Ich kann vorher nicht sagen, wie viele Einträge verwaltet werden müssen.
Ne, Dictionary ist immer schneller bei einer großen Anzahl von Einträgen im vgl. zu einer Liste.
Du machst einfach nur irgendetwas anderes falsch.
Erstelle ein Konsolenprogramm mit zwei Interfaces und entsprechenden Klassen und tacker die mal in ein TDictionary<TGUID, IInterface> rein.
  Mit Zitat antworten Zitat
idefix2

Registriert seit: 17. Mär 2010
Ort: Wien
1.027 Beiträge
 
RAD-Studio 2009 Pro
 
#7

AW: Dictionary statt binärer Suche?

  Alt 7. Aug 2015, 20:08
ich würde auch meinen, dass für diese Aufgabenstellung ein Dictionary adäquat ist.
Sortierte Listen mit Binärsuche sind sinnvoll, wenn du die Daten gelegentich nach dem Schlüssel sortiert auslesen willst, das ist hier sicher nicht der Fall.
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Dictionary statt binärer Suche?

  Alt 8. Aug 2015, 12:02
Komisch, ich habe mir mal zur Fehlersuche den Inhalt des Dictionarys ausgeben lassen.
Dann hat es funktioniert - auch nach Entfernen der Logs.
Da hatte wohl der Linker irgend etwas verwurschtelt...?
Delphi-Quellcode:
// CodeSite.Send('Get:' + IntToStr(MyDict.Count));
// for Key in MyDict.Keys do
// begin
// S1 := Key.AsString;
// Value := nil;
// MyDict.TryGetValue(Key, Value);
// if Assigned(Value) then
// S2 := Value.Guid.AsString
// else
// S2 := 'nil';
// CodeSite.Send(S1 + ': ' + S2);
// end;
      if not MyDict.TryGetValue(aGuid, lGuid) then
        System.SysUtils.Beep;
Ich werde mal mit Dictionarys weiter arbeiten.
Danke für die Infos!
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Dictionary statt binärer Suche?

  Alt 11. Okt 2015, 20: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 22: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
 
#10

AW: Dictionary statt binärer Suche?

  Alt 11. Okt 2015, 22: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
Antwort Antwort
Seite 1 von 6  1 23     Letzte »    


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 20:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz