numerische Keys für TDictionary/TObjectDictionary

[jammernich]

In meinem Programm lade ich viele Dateien nacheinander und jeder Datensatz soll über einen numerischen Wert im Programm angesprochen werden können.

Code: Alles auswählen

uses
  Classes, Generics.Collections;

type
  TDict = specialize TObjectDictionary<Longint, TKlasse>; 

zu den numerischen Keys habe ich eine Frage: Wie soll ich die Keys am besten vergeben damit das Dictionary effizient erstellt werden kann?

fortlaufend: 1-2-3-4..n

zufällig z.B. so: 2345-1-12-345345-3245-612

[af0815]

Die Frage ist vielmehr, wie willst du später die Datensätze effizient ansprechen. Dafür sollte ja der Schlüssel sein. Vergleiche es mit dem Primärschlüssel in einer Datenbank.

[Niesi]

...

zu den numerischen Keys habe ich eine Frage: Wie soll ich die Keys am besten vergeben damit das Dictionary effizient erstellt werden kann?

fortlaufend: 1-2-3-4..n

zufällig z.B. so: 2345-1-12-345345-3245-612

.

Eine Frage, bitte: Wieso die Erwägung auf "zufällig"?

[Warf]

Das ist komplett egal da sie eh gehasht werden. Die Frage ist, wenn du lineare keys hast, warum benutzt du nicht einfach ein Array oder eine Liste?

[Niesi]

Das ist komplett egal da sie eh gehasht werden. Die Frage ist, wenn du lineare keys hast, warum benutzt du nicht einfach ein Array oder eine Liste?

Das mit Liste oder array stimmt.

Aber egal? Wenn "zufällige" keys benutzt werden, so musst Du sicherstellen, dass jeder key einmalig ist - daher verstehe ich noch nicht die Idee mit "zufällig" ...

[photor]

Das ist komplett egal da sie eh gehasht werden. Die Frage ist, wenn du lineare keys hast, warum benutzt du nicht einfach ein Array oder eine Liste?

Die Frage hatte ich mir auch gestellt. So mache ich das:

• üblicherweise lese ich mehrere große Datenfiles (FE-Ergibnisse) ein, die dann miteinander verwurstet werden
• Die werden dann der Reihe nach gescannt und die wichtigen Daten in eine Struktur (eine entsprechend definierte Klasse) gepackt
• diese werden dann in eine TObjectList<TKlasse> gehängt, so dass alle Daten dann erreichbar sind (zumal der Original-Poster ja sowieso schon eine TKlasse definiert hat)..

Den Vorteil eines TDictionaries habe ich nicht gesehen/verstanden - und daher erst einmal nicht gepostet. Sorry.

Also ich würde es auch über eine Liste lösen.

Ciao,
Photor

PS: den grundsätzlichen Vorteil von TDictionary kenne ich schon. Aber wenn sowieso der Key beliebig vergeben wird ... ?

[jammernich]

Hallo zusammen,

@Niesi, Warf: Na wenn es für ein als hashmap impementiertes TDictionary egal ist, genau das wollte ich wissen. Bei einem Dictionary sind die keys immer einzigartig und ich brauche mich darum kaum zu kümmern, außer beim vergeben von keys. Diesen Vorteil sehe ich beim Array gar nicht.

@af0815: Danke, ich habe mir nochmal überlegt wie das "Ansprechen" am vorteilhaftesten wäre - den Dateinamen - als key für das Dictionary zu verwenden. So kann ich noch besser den Überblick behalten und es wird nicht zu kryptisch. Ich schreibe gerade an einem Resourcen-Manager.

@Photor: ich habe eine Art TBaseResource und der Manager soll dann die verschiedenen Resourcen laden z.B. Fonts, Texturen, praktisch alle Assets

Vielen Dank für die Anregungen!

[Warf]

@Niesi, Warf: Na wenn es für ein als hashmap impementiertes TDictionary egal ist, genau das wollte ich wissen. Bei einem Dictionary sind die keys immer einzigartig und ich brauche mich darum kaum zu kümmern, außer beim vergeben von keys. Diesen Vorteil sehe ich beim Array gar nicht.

Naja wenn die Indizes hochzählen kannst du mit einem Array oder einer Liste trotzdem besser dran sein. Eine Hashmap hat normalerweise einen sog. "load factor" von maximal 75% bevor neuer Speicher alloziiert wird. d.h. im Schnitt werden nur 50%-75% des Alloziierten speichers einer Hashmap tatsächlich benutzt.
Wenn du fortlaufende Indizes hast bedeutet das das selbst wenn du im laufe der lebenszeit die hälfte aller Listenindizes verbrennst (also objekte darin freest und die indizes nie mehr anfasst) bist du dennoch effizienter als eine Hashmap.

Hashmaps bringen dir nur was wenn du den Schlüsselraum sehr spärlich besetzt. Also entweder deine Schlüssel eine große Menge abbilden (also z.B. 64 bit Zufallszahlen) oder du nur sehr wenige benutzt. Hashmaps haben zwar in der Landau notation O(1) im Zugriff und O(n) im Speicher, aber mit extrem hohen overhead (speicherverbauch etwa doppelt so hoch wie ein liste und Zugriffszeit ist um mehrere Größenordnungen schlechter). Daher solltest du dir gut überlegen wann du eine Hashmap benutzen willst wenn es auch eine Liste tut