String/Integer Hash

[himitsu]

Allerdings hat man dort keinen Zugriff auf die Hashs.

Delphi-Quellcode:

type
  TMyRec = record
    ID:    Integer;
    Value: String;
  end;
  TIDList := TList<TMyRec>

Wie schnell muß es denn sein?

In der DP gibt es uch noch irgendwo Hashlisten.

Aber wenn es nicht unbedingt extrem schnell sein muß, dann speicher doch die ID in den Objects der TStringList.
In der Liste noch ein LastID gespeichert und jeweils dem neuen Eintrag die nächste ID verpassen, somit könnte man auch Einträge löschen, bzw. den Index unbeachtet lassen.

Im GetFieldName dann die Liste durchgehn und nach der ID suchen ... die paar Integervergleiche dürften ja auch so schon schneller viel sein, als die Stringvergleiche, auch ohne eine sortiete ID-Liste.


Ah, TDictionary ... mit fiehl nur noch sowas wie TKeyValue<> ein, aber keine ganze liste
Bildet das uch eine Hashlist? Ansonsten kommt das etwa auf's Gleiche raus, wie ein selbstimplementiertes Strings+Objects der TStringList.


PS: Bei der THashedStringList dürfen vermutlich keine Werte doppelt vorkommen, also wenn man auch gleiche Strings auseinanderhalten will, bzw. wenn sich der Hash/ID nicht ändern darf, wenn man den String ändert.



[add]
Und zu deiner Speicherersparnis:
250000 * ((12+1 Zeichen) * 2 ByteProChar + mindestens 12 Byte Verwaltungsoffset)
250000 * ((12+1) * 2 + 12)
9500000 Byte
9,1 MB

OK, gegenüber 1 MB, mit der Integerlistenvariante, klingt das schon irgendwie "mehr", aber was sind heute schon 10 MB?

PS: Wo kommen die Strings denn her?
Strings besitzen eine Referenzzählung, also wenn sie alle aus den selben 500 Quellen kommen, dann belegen die insgesammt sogar weniger Speicher, als deine Integervariante, da die zusätzliche ID/String-Liste eingespart wird und SizeOf(String) = SizeOf(Integer)

Und wenn das alles Konstanten sind, dann belegen die sogar noch weniger Speicher, da die Stringdaten nicht wirlich im rbeitspeicher liegen, sondern in der EXE verbleiben, bzw. in deren Datenbereich, welcher nur als eine Art MMF temporär im RAM liegt.

[jaenicke]

Zitat von himitsu:

Ah, TDictionary ... mit fiehl nur noch sowas wie TKeyValue<> ein, aber keine ganze liste
Bildet das uch eine Hashlist?

Ja, das Dictionary wird auch gehasht.

[Linor]

Danke für die Hinweise

Für mich optimal war das TDictionary<Cardinal, String> in Kombination mit dem recht schnellen ELF-Hash, beim Hinzufügen wird Add(HashOfString, String) abgelegt und der Hash wird sich gemerkt. Mit dem Hash kann ich dann direkt auf Elemente zugreifen

Kennt vielleicht jemand einen anderen, noch schnelleren Hash?

[jaenicke]

Zitat von Linor:

Kennt vielleicht jemand einen anderen, noch schnelleren Hash?

Wie schnell der interne Hash von TDictionary ist, weiß ich nicht, aber hast du den mal versucht? Also einfach TDictionary<string, string>?

[himitsu]

Eventuell eine Speicherfragmentierung?

Und wo hst du den Wert abgelesen?
Im Taskmanager gibt nicht den tatsächlichen Verbrauch wieder, da FastMM sich einige Daten behält, um sie schneller wieder verwenden zu können, anstatt sie immer neu vom System anzufordern.

In der System-Unit gibt es Funktionen, womit du den FastMM nach seinem tatsächlichen Speicherzustand befragen kannst.

[Linor]

Habe ich sowohl mit GetProcessMemoryInfo also auch im TaskManager abgelesen... Ich denke mal das die Strings im Schnitt länger sind als gedacht und das die Objekte noch weitere Objekte haben die wieder Strings haben, so eine Art rekursivität

BTW: Weiss jemand ob man ein TDictionary<Integer, String> sortiert abfragen kann?
Also for field in Fields.Values do.... Im Moment kommen die "irgendwie"... Habe mir damit beholfen die in eine sortierte TStringList zu kopieren, via l.Add(Format('%.10d',[field.Index]), field)...

[Linor]

Zitat von jaenicke:

Zitat von Linor:

Kennt vielleicht jemand einen anderen, noch schnelleren Hash?

Wie schnell der interne Hash von TDictionary ist, weiß ich nicht, aber hast du den mal versucht? Also einfach TDictionary<string, string>?

Wie würde das gehen? Habe mal gemessen, der Elf hashed 10.000 Strings a 10 Zeichen in 1ms, denke das ist mehr als ausreichend für mich

[jaenicke]

Zitat von Linor:

Zitat von jaenicke:

Zitat von Linor:

Kennt vielleicht jemand einen anderen, noch schnelleren Hash?

Wie schnell der interne Hash von TDictionary ist, weiß ich nicht, aber hast du den mal versucht? Also einfach TDictionary<string, string>?

Wie würde das gehen?

Einfach nicht hashen, sondern direkt den String angeben.

Zitat von Linor:

BTW: Weiss jemand ob man ein TDictionary<Integer, String> sortiert abfragen kann?

Delphi-Quellcode:

var
  test: TDictionary<string,string>;
  ValueArray: TArray<string>;
  CurrentValue: string;
begin
  test := TDictionary<string,string>.Create;
  try
    test.Add('a1', 'bb');
    test.Add('a2', 'abb');
    test.Add('a3', 'cbb');
    test.Add('a4', 'xbb');
    ValueArray := test.Values.ToArray;
    TArray.Sort<string>(ValueArray);
    for CurrentValue in ValueArray do
      ShowMessage(CurrentValue);
  finally
    test.Free;
  end;

[Blup]

Ein Hash lässt sich nicht unbedingt eindeutig einem String zuordnen.
Es kann für einen Hash also mehrere gültige Strings geben.

Das primäre Problem wurde bereits angesprochen.
Warum werden für die Feldnamen bei der Erzeugung einer Objekt-Instanz jedesmal neue Strings erzeugt?

Mit Konstanten wird für jedes Feldobjekt nur ein Zeiger benötigt:

Delphi-Quellcode:

constructor TMyData.Create();
begin
  inherited;
  FID          := TMyField.Create(Self, 'ID');
  FBezeichnung := TMyField.Create(Self, 'BEZEICHNUNG');
  FTag1        := TMyField.Create(Self, 'TAG1');
  FTag2        := TMyField.Create(Self, 'TAG2');
  FTag3        := TMyField.Create(Self, 'TAG3');
  FTag4        := TMyField.Create(Self, 'TAG4');
  FTag5        := TMyField.Create(Self, 'TAG5');
  FTag6        := TMyField.Create(Self, 'TAG6');
  FTag7        := TMyField.Create(Self, 'TAG7');
end;

oder

const
  TagFieldName: array [1..7] of string = ('TAG1', 'TAG2', 'TAG3', 'TAG4', 'TAG5', 'TAG6', 'TAG7');

constructor TMyData.Create();
begin
  inherited;
  FID          := TMyField.Create(Self, 'ID');
  FBezeichnung := TMyField.Create(Self, 'BEZEICHNUNG');
  for i := 1 to 7 do
    FTag[i] := TMyField.Create(Self, TagFieldName[i]);
end;

aber nicht! so:

constructor TMyData.Create();
begin
  inherited;
  FID          := TMyField.Create(Self, 'ID');
  FBezeichnung := TMyField.Create(Self, 'BEZEICHNUNG');
  // für jedes Feld in jeder Instanz einen neuen String erzeugen!
  for i := 1 to 7 do
    FTag[i] := TMyField.Create(Self, 'TAG' + IntToStr(i)); 
end;

Falls das nicht möglich ist, könnte man TMyField.Create überschreiben.
Die übergebene Zeichenkette wird in einem globalen Dictionary gesucht.
Wenn erforderlich, wird dieses ergänzt.
Der String aus dem Dictionary wird als Feldname verwendet, es erhöht sich nur dessen Referenzzähler.
Wird der übergebene String nicht weiter verwendet, wird der Speicher dafür automatisch freigegeben.

[Linor]

Hallo,

Zitat von himitsu:

9,1 MB
OK, gegenüber 1 MB, mit der Integerlistenvariante, klingt das schon irgendwie "mehr", aber was sind heute schon 10 MB?

nachdem ich das implementiert hatte, konkret geht es hier um Feldnamen in einem TMyField und einem TMyDataRecord, hatte ich bei 30.000 Datensätzen eine Einsparung von knapp 150MB, weiss nicht wie Zahlen zu stande kommen, aber ist halt so...

Mein erster Ansatz mit der TStringList zeigte das ja schon, aber die war halt zu langsam