AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

TDictionary<K,V> und Kapazität

Ein Thema von ventiseis · begonnen am 4. Mär 2020 · letzter Beitrag vom 5. Mär 2020
Antwort Antwort
ventiseis

Registriert seit: 15. Jan 2009
Ort: 94032 Passau
43 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#1

TDictionary<K,V> und Kapazität

  Alt 4. Mär 2020, 21:15
Delphi-Version: 10.2 Tokyo
Hallo,

während einer längeren Debugging-Session ist mir etwas aufgefallen. Bekannt ist:
  • man kann ein TDictionary<K,V> mit einer bestimmten Kapazität über den Konstruktor erzeugen (siehe TDictionary.Create)
  • ein Dictionary hat immer einen gewissen Füllgrad
  • die Einträge des Dictionaries werden in ein Array aus Buckets einsortiert
  • ist der Füllgrad erreicht, dann muss das Bucket-Array vergrößert werden, ansonsten wird der Lookup im Dictionary ineffizient
In der Implementierung von TDictionary wurde das so umgesetzt:
  • die Kapazität ist immer die nächstgrößere Zweierpotenz, aber mindestens 4 Buckets
  • der Füllgrad wird berechnet: (Kapazität shr 1) + (Kapazität shr 2)

Das führt aber dazu, dass bei manchen Kapazitätswerten nicht mehr alle Einträge ins Dictionary passen und das Dictionary beim Hinzufügen von Elementen vergrößert werden muss, obwohl man eine ausreichende Kapazität angegeben hat:

Kapazität / Konstruktorverwendete KapazitätMax. Füllgrad 
443Kapazität im Konstruktor nicht ausreichend
203224Kapazität ausreichend
293224Kapazität wieder nicht ausreichend

Mein Fazit: falls man Reallokationen vermeiden will, sollte man die Kapazität des Dictionaries größer angeben als die Anzahl der Elemente, weil der Füllgrad bei der Kapazitätsberechnung nicht einbezogen wird.

Ist das auch schon mal jemand aufgefallen? Oder habe ich hier ein Verständnisproblem?
Bastian
  Mit Zitat antworten Zitat
ventiseis

Registriert seit: 15. Jan 2009
Ort: 94032 Passau
43 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#2

AW: TDictionary<K,V> und Kapazität

  Alt 4. Mär 2020, 21:17
Hier ein Testprogram zum Auslesen des Füllgrads für Delphi 10.2:

Delphi-Quellcode:
program Project7;

{$APPTYPE CONSOLE}

{$R *.res}

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

function GetGrowThreshold(AInstance: TObject): NativeUInt;
var
  LContext: TRttiContext;
  LType: TRttiType;
  LField: TRttiField;
begin
  LContext := TRttiContext.Create();
  LType := LContext.GetType(TDictionary<Integer, Integer>);
  LField := LType.GetField('FGrowThreshold');
  Result := LField.GetValue(AInstance).AsType<Integer>;
end;

var
  I: Integer;
  LDictionary: TDictionary<Integer, Integer>;

const

  C = 20;

begin
  LDictionary:=TDictionary<Integer, Integer>.Create(C);
  try

    for I := 1 to C do
    begin
      LDictionary.Add(i,i);
      WriteLn(IntToStr(i) + ': ' + GetGrowThreshold(LDictionary).ToString);
    end;
    ReadLn;
  finally
    FreeAndNil(LDictionary);
  end;
end.
Bastian
  Mit Zitat antworten Zitat
Benutzerbild von Stevie
Stevie

Registriert seit: 12. Aug 2003
Ort: Soest
3.683 Beiträge
 
Delphi 10.1 Berlin Enterprise
 
#3

AW: TDictionary<K,V> und Kapazität

  Alt 5. Mär 2020, 09:49
Ja, das stimmt. Die Kapazität, die man angibt stimmt nicht mit der Anzahl der Elementen überein, die man ohne Grow hinzufügen kann.
Stefan
“Simplicity, carried to the extreme, becomes elegance.” Jon Franklin

Delphi Sorcery - DSharp - Spring4D - TestInsight
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

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 22:41 Uhr.
Powered by vBulletin® Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf