Dictionary statt binärer Suche?

[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 von idefix2:

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 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 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 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 von 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?

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 von Union:

Ich denke @Stahli misst Mist

Das verbitte ich mir!
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 von Sir Rufo:

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?