String/Integer Hash

[Linor]

Hallo Zusammen,

ich suche für folgendes ein Ersatz:

FFieldNames = TStringList

Delphi-Quellcode:

function GetFieldIndex(Name: String): Integer;
var
   idx: Integer;
begin
   idx := FFieldNames.IndexOf(Name);
   if ( idx >= 0 ) then
      Exit(idx);

   Result := FFieldNames.Add(Name);
end;

function GetFieldName(Idx: Integer): String;
begin
   Result := FFieldNames[Idx];
end;

Es geht darum das immer wiederkehrende Strings in einer Liste gespeichert und jeder String eine eindeutige Id bekommt. Die Id wird als Integer "gemerkt" und später wenn der benötigt wird dann per Index wieder abgegriffen... Es handelt sich dabei um ca. 500 Einträge, die dann auf bis 50.000 x 50 Werte verteilt werden, es stehen als 250.000 * 12 Zeichen (im Schnitt), gegen 250.000 Integer, die speicherersparnis ist enorm :-D

Mein Knackpunkt: Laaaaangsam :( Nachteil dabei ist, ich kann FFieldNames nicht auf "Sorted" setzen, da sonst beim Hinzufügen der Index vorhandener Einträge sich verändert und später GetFieldName nur murks liefert.

Jemand eine performante Lösung dafür?

[CCRDude]

In der Unit IniFiles gibt es eine THashedStringList :)

[jaenicke]

Bei Delphi 2010 fällt mir spontan ein generisches TDictionary<TKey,TValue> ein. Das lässt sich ja bei Bedarf auch doppelt nutzen um in beiden Richtungen schnell zu sein. ;-)

[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 :oops:
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:

Zitat von himitsu (Beitrag 1133707)

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

Ja, das Dictionary wird auch gehasht.

[Linor]

Danke für die Hinweise :-D

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 :thumb:

Kennt vielleicht jemand einen anderen, noch schnelleren Hash?

[Linor]

Hallo,

Zitat:

Zitat von himitsu (Beitrag 1133707)

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... :shock:

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

[jaenicke]

Zitat:

Zitat von Linor (Beitrag 1133808)

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