Dictionary statt binärer Suche?

[stahli]

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.

[Der schöne Günther]

Das was du bei einem

Delphi-Quellcode:

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:

Delphi-Quellcode:

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.

[TiGü]

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?

[stahli]

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

[Dejan Vu]

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.

[TiGü]

Zitat:

Zitat von stahli (Beitrag 1311412)

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.

[idefix2]

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.

[stahli]

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]

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?

[Sir Rufo]

Um das Verhalten eines Typen als Key in einem Dictionary zu untersuchen, schaut man sich einfach die Ergebnisse vom zugehörigen IEqualityComparer an, den man durch Abfrage von

Delphi-Quellcode:

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

Delphi-Quellcode:

IEqualityComparer<TGuid>

mitliefern.

[stahli]

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

[Sir Rufo]

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

[stahli]

Super, dann sollte alles passen.
Danke!

[Sir Rufo]

Zitat:

Zitat von stahli (Beitrag 1318442)

Super, dann sollte alles passen.
Danke!

Nur dass es so eben langsam ist ... und wolltest du nicht gerade wegen schnell auf ein Dictionary umsteigen?

[stahli]

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?

[Sir Rufo]

Nun ja, du hast jetzt eine GetHashCode-Methode die wesentlich schneller als die Equals-Methode ist.

Nur wird diese GetHashCode-Methode immer nur einmal aufgerufen und die Equals-Methode für jeden Eintrag in dem Bucket.

Was ist denn jetzt wohl besser? Eben, GetHashCode sollte nicht langsam, aber auch nicht zu einfach sein und bei ähnlichen Werten sehr unterscheidliche Hash-Werte liefern. Im Idealfall bekommst du einen HashCode ohne Kollisionen und der Key wird mit einem Aufruf der Hash-Funktion und einem Aufruf der Vergleichs-Funktion gefunden oder eben nicht.

Dann wird es schnell.

Siehe dazu auch Hashfunktion - Kriterien für eine gute Hashfunktion
(wir brauchen aber Ordnung und kein Chaos -> also eine stabile Hash-Funktion)

Ein Gegenbeispiel für deine wenigen Töpfe:

Pack mal alle deine Sachen in Container (pro Farbe einen Container) und jetzt suche nach einer schwarzen Socke. Dauert wie lange?
Pack jetzt alle deine Sachen in Container (pro Farbe, Art, Größe, Hersteller, ... einen Container) und jetzt suche nach den schwarzen Wintersocken von Ergee. Dauert wie lange? Eben einfach zum passenden Container gehen und eins von den drei Paaren herausnehmen, fertig.

Genau so geht es dem Dictionary auch ;)

[stahli]

Hmm, ich sehe nicht, warum meine jetzige Lösung dann langsam sein soll.
Ich nutze Integerwerte 0..99999, die relativ gleichmäßig verteilt sind.
Also sind nachher bis 100.000 Töpfe vorhanden, die irgendwann einige Einträge enthalten.

Als alternatives Kriterium könnte ich meinen zweiten Zeitstempel nehmen. Der ist weitestgehend eindeutig, sollte also i.d.R. nur einmal im Projekt vorliegen.
Jetzt könnte ich mir vorstellen, aus dem Zeitstempel einen Integerwert zu berechnen - aber was wäre da sinnvoll?

-> Z.B. fC * Succ(SekundenDesZeitstempels) ? Das würde einen größeren Wertebereich bringen.


Und ist es nicht so, dass das Dictionary die Bucket-Nr erst aus dem Integerwert berechnet (anhand der aktuellen Größe der Liste).
Dann ist also der Integerwert nicht direkt die Nr. des Buckets.


Echt peinlich solche Fragen. :oops:

[Sir Rufo]

Probier es doch einfach mit unterschiedliche Hash-Funktionen aus und teste dann mit einer vergleichbaren Beispielmenge, so wie das auch in deiner Anwendung zu erwarten wäre.

Dann bekommst du ein Gefühl dafür ...

[Dejan Vu]

Vielleicht als Anmerkungen:

1. Man muss sich keine großartigen Gedanken um eine Hashfunktion machen. Kann man, muss man aber nicht. Wenn die Daten einen eindeutigen Schlüssel haben (integer, string egal) reicht das. Man kann auch einen zusammengesetzten Schlüssel nehmen und string daraus basteln. Bei strings nehme ich eh den Elf-Hash, der ist bisher immer ausreichend gewesen. Hauptsache, der ursprüngliche Schlüssel identifiziert das Objekt eindeutig.
2. Wenn man einen reinen Integer-Dictionary nimmt, reicht es i.a. sich für die Größe der Tabelle eine Primzahl auszusuchen, um Kollisionen genügend zu vermeiden. Das sollte aber die Dictionary sowieso machen, weswegen es ausreicht, bei einem Integer-Key diesen Key selbst als Hashfunktion zu verwenden.
3. Eine gute Dictionary-Implementierung erkennt von alleine, wenn die Anzahl der Kollisionen zu hoch ist und vergrößert sich selbst.

Welche Hashfunktion man für eine UUID benutzen könnte, ist hier ganz gut beschrieben bzw. getestet.
http://programmers.stackexchange.com...ness-and-speed

[stahli]

@Sir Rufo
Also so völlig ohne Plan macht das m.E. keinen Sinn.

@Dejan Vu
Die Bilder sehen schön bunt aus. :-)
Sehr viel mehr verstehe ich da leider nicht. :oops:
Bis sich das Gegenteil erweist vertraue ich einfach mal drauf, dass das Dict mit meinem Integer gut zurecht kommt...

[stahli]

Oh, ich habe jetzt mal mein Dictionary mit einer binären Liste (also Liste mit binärer Suche) ersetzt.

Es werden 420.000 Objekte erzeugt und gespeichert.
Das Ergebnis überrascht mich:

Dictionary:
420.000: (00:00:01) -> 00:06:57

Binäre Liste: (aufsteigend)
420.000: (00:00:00) -> 00:00:04

Binäre Liste: (absteigend)
420.000: (00:00:00) -> 00:00:30


Die ID´s, nach denen sortiert wird, ist hier immer aufsteigend.
Daher wurden neue Objekte in der aufsteigenden Liste immer nur angehängt.
Damit neue Objekte auch mal (bzw. immer) eingefügt werden, habe ich auch mal absteigend sortiert.

Damit ist die Liste hier für mich deutlich schneller und attraktiver.

Der Grund dafür ist (sofern der Fehler nicht hausgemacht ist), dass das Dictionary immer mal Zeit braucht, um sich bei bestimmten Größenüberschreitungen neu zu strukturieren.
Das benötigt ziemlich viel Zeit.
bei 197.000: (00:00:25)
bei 394.000: (00:02:55)

Womöglich ändert sich das Verhältnis bei noch sehr viel größeren Listen, vor allem wenn man das Dictionary schon von vorn herein mit einer ausreichenden Größe anlegt.


Ein Baum wäre ja auch noch eine Option, wie hier diskutiert: http://www.delphipraxis.net/178549-i...iert-sein.html

[Sir Rufo]

Delphi-Quellcode:

var
  lDict: TObjectDictionary<TObject, integer>;
  lSw  : TStopwatch;
begin
  lDict := TObjectDictionary<TObject, integer>.Create( [ doOwnsKeys ] );
  try
    lSw := TStopwatch.StartNew;
    while lDict.Count < 1000000 do
      begin
        lDict.Add( TObject.Create, 0 );
      end;
    lSw.Stop;
  finally
    lDict.Free;
  end;

  ShowMessage( lSw.ElapsedMilliseconds.ToString( ) );
end;

dauert 179ms.

Die Langsamkeit ist somit hausgemacht und wird wohl an einer schlechten Hash-Funktion (langsam bzw. zu viele Kollisionen) liegen.

[idefix2]

@SirRufo
Irgendwie verstehe ich überhaupt nicht, was du da machst.

Laut Dokumentation:

Code:

TObjectDictionary<TKey,TValue> = class(TDictionary<TKey,TValue>);

Key ist das TObject, Value ist der integer? Sollte es nicht andersrum sein?

Und alle Objekte sind leer, das Create allein tut doch gar nichts, und das TObject sieht doch gar keine Daten vor, die gibt es doch erst in den abgeleiteten Objekten. Was kann da bei einer Hashfunktion rauskommen? Gibt es da nicht nur Kollisionen?

[Union]

Ja, ich glaube auch dass es eher so sein müsste:

Delphi-Quellcode:

uses
  System.SysUtils,
  System.Generics.Collections,
  System.Diagnostics;

var
  lDict: TObjectDictionary<Integer, TObject>;
  lSw : TStopwatch;
  I : Integer;
begin
  lDict := TObjectDictionary<Integer, TObject>.Create( [ doOwnsValues ] );
  try
    lSw := TStopwatch.StartNew;
    I   := 0;
    while I < 1000000 do
    // Der Aufruf von Count macht ca 50% der Laufzeit aus.
    // while lDict.Count < 1000000 do
    begin
      Inc(I);
      lDict.Add( I, TObject.Create);
    end;
    lSw.Stop;
  finally
    lDict.Free;
  end;

  writeln( lSw.ElapsedMilliseconds.ToString( ) );
  Readln;
end.

Ändert aber nichts am eigentlichen Problem mit der Laufzeit. Ich denke @Stahli misst Mist ;)

[Mavarik]

Zitat:

Zitat von idefix2 (Beitrag 1324498)

Key ist das TObject, Value ist der integer? Sollte es nicht andersrum sein?

Der Value ist doch egal für die Sortierung. Mit dem TObject als Key hat "er" dadurck immer einen Pointer der sortiert werden muss...

[Sir Rufo]

Fangen wir einmal von vorne an:

• Ein Dictionary ist eine Key-Value-Menge
• Für die Einsortierung braucht das Dictionary einen IEqualityComparer<TKey>
• Dieser Comparer liefert für den Key eine Hash-Funktion und eine Gleichheits-Funktion

Wenn jetzt der Key von

Delphi-Quellcode:

TObject

abgleitet ist (also eine Klasse), dann geht der Standard-EqualityComparer auf die Methoden:

Delphi-Quellcode:

function TObject.Equals( Obj:TObject ) : Boolean; virtual;
function TObject.GetHashCode() : Integer; virtual;

Wenn

Delphi-Quellcode:

TObject.GetHashCode

nicht überschrieben wurde, dann wird dort der Referenz-Zeiger als Integer-Wert zurückgeliefert (bei x64 etwas anders).

Somit haben wir dort garantiert keine Kollisionen.

Das wollte ich damit nur zeigen. Keine Kollisionen -> Dictionary ganz schnell.
Wird das Dictionary langsam, dann hat man Mukrs beim HashCode gebaut.

Und

Delphi-Quellcode:

TDictionary<TObject,Integer>

ist absolut bewusst, da ich das Dictionary hier als ein HashSet missbrauche.

[idefix2]

Wenn ein Objekt als Key zum Sortieren übergeben wird, dann sollte doch normalerweise nach dem Inhalt des Objekts (den es nicht gibt) sortiert werden und nicht nach dem Pointer, oder sehe ich das falsch?

edit:
Ok, ich war schneller als Sir Rufo mir seiner Antwort, bzw. hat sich das überschnitten. Wenn gethashcode vom TObject den Referenz-Zeiger liefert, ist alles klar, dann funktioniert das. Ist allerdings etwas verwirrend.

[Sir Rufo]

Zitat:

Zitat von idefix2 (Beitrag 1324515)

Wenn ein Objekt als Key zum Sortieren übergeben wird, dann sollte doch normalerweise nach dem Inhalt des Objekts (den es nicht gibt) sortiert werden und nicht nach dem Pointer, oder sehe ich das falsch?

Ein Dictionary ist keine sortierte Liste sondern eine HashSet mit einem Wert pro Schlüssel.

Genauso wie eine Waschmaschine kein Toaster ist, obwohl beide einen Stromanschluss haben, eine Öffnung um etwas hineinzustecken und einen Schalter zum einschalten.

[stahli]

Zitat:

Zitat von Union (Beitrag 1324501)

Ich denke @Stahli misst Mist ;)

Das verbitte ich mir! :stupid:
Die Zeiten messe ich schon richtig.

In Tausender-Schritten braucht der Import jeweils unter 1 Sekunde (da wird jeweils noch ein wenig mehr getan als nur ein Create).
Zweimal dauert es aber deutlich länger:
bei 197.000: (00:00:25)
bei 394.000: (00:02:55)


Es liegt offenbar wirklich daran, dass der Hashwert ungünstig ermittelt wird.

Da ich es aber nicht besser weiß und mit einer Liste ohnehin besser zurecht komme, bleibe ich bei der Liste und bin zufrieden.

[idefix2]

Zitat:

Zitat von Sir Rufo (Beitrag 1324517)

Genauso wie eine Waschmaschine kein Toaster ist, obwohl beide einen Stromanschluss haben, eine Öffnung um etwas hineinzustecken und einen Schalter zum einschalten.

Bist du dir da ganz sicher? :wink:

[Sir Rufo]

Zitat:

Zitat von idefix2 (Beitrag 1324519)

Zitat:

Zitat von Sir Rufo (Beitrag 1324517)

Genauso wie eine Waschmaschine kein Toaster ist, obwohl beide einen Stromanschluss haben, eine Öffnung um etwas hineinzustecken und einen Schalter zum einschalten.

Bist du dir da ganz sicher? :wink:

Ja, merkt man dann, wenn man morgens schon Schaum vor dem Mund hat :stupid:

[bernau]

Zitat:

Zitat von Sir Rufo (Beitrag 1324514)

Und

Delphi-Quellcode:

TDictionary<TObject,Integer>

ist absolut bewusst, da ich das Dictionary hier als ein HashSet missbrauche.

Aber ist es nicht so, das der TE anhand der GUID das Interface/Object geliefert haben möchte? Dann sollte doch die GUID im KEY stehen und nicht das Interface/Object.

[stahli]

Der Sir wollte nur zeigen, dass die Anzahl der Einträge letztlich kein Problem darstellt, was ich nun auch einsehe.

Offenbar muss man aber für die Berechnung des Hashwertes eine optimale Lösung finden, was mir vorliegend nicht gelungen ist.

Deshalb hat sich mein Dic nicht performant genug verhalten.

Aber ich habe mit der einfachen sortierten Liste eine für mich sehr gut passende Alternative, mit der ich sehr gut zurecht komme.

[Sir Rufo]

@stahli :thumb:

[einbeliebigername]

Hallo,

es lässt mir keine Ruhe, ich muss auch mal was dazu sagen. Erstmal die Frage ob sich jemand die Implementierung von TDictionary<TKey,TValue> angeschaut hat? Denn ich glaube die Implementierung ist das Problem.

Zitat:

Zitat von Sir Rufo (Beitrag 1324517)

Ein Dictionary ist keine sortierte Liste sondern eine HashSet mit einem Wert pro Schlüssel.

Was ist denn ein HashSet? Ich kenne nur den Begriff Hashtabelle, welche sich nach meinem Kenntnisstand (und da lasse ich mich gern eines Besseren belehren) kollisionsfest auf zwei Arten implementieren lassen:

Delphi-Quellcode:

// Hash-Wert ist der 1.Index im zweidimensionalen Array
THashTable= array of array of record
  Key: TKey;
  Value: TValue;
end;

oder

Delphi-Quellcode:

THashTable= array of record
  Hash: THash; // Array ist nach Hash sortiert, Zugriff mittels binärer Suche nach dem Hash
  Values: array of record
    Key: TKey;
    Value: TValue;
  end;
end;

Folgende Aussagen meinerseits beziehen sich auf die Implementierung vom TDictionary<TKey,TValue> im Delphi-XE8.

Leider wird keine der Varianten benutzt. Die Implementierung ist sicherlich Creative. Ob sie auch Klever ist, wage ich zu bezweifeln.

Zitat:

Zitat von Mavarik (Beitrag 1324507)

Der Value ist doch egal für die Sortierung. Mit dem TObject als Key hat "er" dadurck immer einen Pointer der sortiert werden muss...

Im Dictionary wird gar nicht sortiert. Jedenfalls kann ich das Sortierkriterium nicht erkennen.

Zitat:

Zitat von Sir Rufo (Beitrag 1324514)

Wenn

Delphi-Quellcode:

TObject.GetHashCode

nicht überschrieben wurde, dann wird dort der Referenz-Zeiger als Integer-Wert zurückgeliefert (bei x64 etwas anders).

Somit haben wir dort garantiert keine Kollisionen.

Im x64 haben wir wohl Kollisionen, da der Hashwert 32 Bit hat und die Pointer 64 Bit haben. Und dann ist im Dictionary der Dreh- und Angelpunkt die Funktion:

Delphi-Quellcode:

function TDictionary<TKey,TValue>.GetBucketIndex(const Key: TKey; HashCode: Integer): Integer;
var
  start, hc: Integer;
begin
  if Length(FItems) = 0 then
    Exit(not High(Integer));

  start := HashCode and (Length(FItems) - 1);
  Result := start;
  while True do
  begin
    hc := FItems[Result].HashCode;

    // Not found: return complement of insertion point.
    if hc = EMPTY_HASH then
      Exit(not Result);

    // Found: return location.
    if (hc = HashCode) and FComparer.Equals(FItems[Result].Key, Key) then
      Exit(Result);

    Inc(Result);
    if Result >= Length(FItems) then
      Result := 0;
  end;
end;

Für mich ist bei diesem Algorithmus der ermittelte Startindex der eigentliche Hash, denn wenn an der Stelle das Gesuchte nicht liegt, wird anschließend eine sequenzielle Suche durchgeführt, was man wegen teuer ja nicht will. Und bei meinen Versuchen mit TObjectDictionary<TObject,Integer> bekommen sehr viele Objekte den gleichen Startindex.

Und wenn man sich dann noch

Delphi-Quellcode:

Grow

und vor allem

Delphi-Quellcode:

Rehash

anschaut sieht man auch wieso Stahli das misst was er misst.

Also immer schön überprüfen ob die eingesetzten Klassen auch das leisten, weswegen man sie einsetzt.

einbeliebigername.

[stahli]

Bei Video2Brain ist ein interessantes Tutorial zu Datenstrukturen und darin auch zu Hash-basierten Strukturen.
https://www.video2brain.com/de/video...atenstrukturen
Ist halt leider kostenpflichtig.

Das ist recht einfach gehalten und daher gut verständlich.

Was Emba im Detail umgesetzt hat kann ich nicht wirklich nachvollziehen.
Insbesondere erschließt sich mir nicht, was ich beachten müsste, um effektive Hashwerte zu erhalten.

Aber wie gesagt. Ich komme derzeit auch sehr gut ohne aus.

PS: Ich meine mich zu erinnern, dass AQTime genau auch Grow und Rehash als Bremse ausgemacht hatte. Und ich hatte daraus dann interpretiert, dass ich das dann nicht ändern kann, weil das ja ein Verhalten der Komponente ist.

[Sir Rufo]

Wenn man etwas nicht nicht weiß, dann kann man die gute Tante fragen HashSet.

Und ein HashSet ist eine Menge von eindeutigen Werten.

Wenn die Implementierung so schlecht ist, was habe ich denn dann falsch gemacht wenn bei mir 1.000.000 Instanzen da in 179ms reinflutschen? :gruebel:

[idefix2]

Diese Implementierung ist allerdings ziemlich miserabel.
Für eine brauchbare Hashtabelle braucht man entweder ein zweidimensionales Feld, oder eine Familie von Hashfunktionen, durch die man sicherstellt, dass keine "Ballungen" von Kollisionen auftreten.

Wenn ein eindimensionales Hashfeld verwendet und bei einer Kollision einfach immer der nächsthöhere Index genommen wird, entstehen immer grössere Blöcke von bereits besetzten Indizes, und wenn ein neuer Hashwert irgendwo in so einen Block hineinfällt, vergrössert sich der besetzte Block weiter und damit 1. die Wahrscheinlichkeit, dass irgend ein Hashwert wieder in diesen Block fällt und ihn weiter verlängert, und 2. natürlich die durchschnittliche Suchzeit nach jedem Schlüssel, dessen Hashberechnung irgendwo in diesem besetzten Block aufschlägt.

@ Sir Rufo
Die Verwendung von der Reihe nach angelegten Speicheradressen als Index ist eine absolut atypische Anwendung. Nachdem ein TObject eine Anzahl n Bytes braucht und das nächste TObject typischerweise die Adresse des vorigen TObject + n erhält, wird hier die Problematik der Kollisionsballungen automatisch entschärft. Bei zufälligen Werten für den Index hast du in aller Regel keine so optimal-gleichmässige Verteilung der Schlüsselwerte (die durch das "and" bei der Erzeugung des Hashindex eine optimal-gleichmässige Verteilung der Hashwerte über die ganze Breite der Hashtabelle ergibt).

[einbeliebigername]

Zitat:

Zitat von Sir Rufo (Beitrag 1324546)

Wenn die Implementierung so schlecht ist, was habe ich denn dann falsch gemacht wenn bei mir 1.000.000 Instanzen da in 179ms reinflutschen? :gruebel:

Du vergleichst Äpfel mit Birnen. Deine Pointer werden durch ein Cast in die Hash-Werte gewandelt. Stahli's Guids sind aber 128 Bit breit und da muss schon gerechnet werden um die Hash-Werte zu bekommen. Und dann ist bei solchen Algorithmen leider nicht nur die Anzahl der Elemente, sonder auch ihre Verteilung und Reinfolge ausschlaggebend. [nur dahingesagt]Ist schon ein Unterschied ob man die Schlüsselmenge

Delphi-Quellcode:

[1, 2, 3, 4, ...]

oder

Delphi-Quellcode:

[4, 8, 12, 16, ...]

hat, auch wenn beide 1.000.000 Elemente haben.[/nur dahingesagt]

@idefix2: +100

einbeliebigername.

[Sir Rufo]

Warum war denn wohl mein erstes Fazit, dass der Hash-Algorithmus von stahli das Problem verursacht (zu langsam oder zu viele Kollisionen)? :roll:

Bei einer Entität ist die ID das ausschlaggebende Kriterium. Die ist gerne mal ein

Delphi-Quellcode:

integer

und wird fortlaufend (Datenbank) vergeben. Da wird es sogar egal, wo die Instanz im Speicher liegt, der Hashwert wird über die ID erzeugt.

Hier haben wir eine GUID. Na und, dann eben den Hashwert davon bilden. Aber mit Sinn und Verstand. Und wenn das Erzeugen zu lange dauert, dann einfach mit einem Cache des Wertes (muss ja eh ein stabiler Hashwert sein).