Anregungen: Verwalten einer "Dynamischen Menge"

[Dirty Oerti]

Tag zusammen

Ich bin auf der Suche nach Anregungen, wie ich ein Problem möglichst optimal lösen kann.
Und zwar möchte ich eine Menge an Objekten (der gleichen Klasse) verwalten. Die Größe der Menge ändert sich zur Laufzeit mitunter aber drastisch.
Ich bin aber nur in der Lage, 4KB große Blöcke anzufordern oder freizugeben. (Ja ja ..)

Jedes einzelne Element möchte ich möglichst schnell erreichen können, über eine eindeutige Identifikationsnummer z.B.
Allerdings soll sich der Speicherbedarf auch am Minimum bewegen, sprich, ich will nicht zu viel ungenutzten Speicher haben.

Meine ersten Überlegungen gingen hin zu einer "Liste" aus diesen 4KB Blöcken, in jedem eine gewisse (aber fest bekannte) maximale Menge an Objekten sowie eine kleine Tabelle mit den enthaltenen Identifikationsnummern (oder auch nur Start & Ende)
Wenn einer dieser Blöcke beim Löschen nun zu leer wird (und ein benachbarter Block ebenfalls leerer wird), dann könnte man diese Blöcke ja leicht zusammenlegen zu einem Block, und so den Speicherplatzbedarf der gesamten Struktur wieder minimieren.

Ideen oder Kritik zu meinem Konzept, bzw zu meiner Problemstellung?
Ist das Problem, bzw das, was ich erreichen will, verständlich?
Unter Umständen kann ich das auch noch als Skizze verdeutlichen, nur sitz ich grad im Zug (ein Regional Express) und da ist es mit GIMP immer etwas schwierig ^^

LG
Daniel

[cloidnerux]

Wie wäre es mit einer Hashtable?

[Kerli]

Jedes einzelne Element möchte ich möglichst schnell erreichen können, über eine eindeutige Identifikationsnummer z.B.

Wie meinst du das genau? Reicht es hier aus einen Index in einem Array bzw. einen Zeiger auf die Speicherposition zu haben?

Eine Möglichkeit die ich schon öfters gesehen habe, ist es sich den letzten freigewordenen Speicherblock zu merken und wenn ein neuer Speicherblock freigegeben wird die Adresse/Index etc. auf den alten letzten freien Speicherblock in den neuen speichern, um so immer in O(1) einen freien Block zu erhalten. Beim Vergeben nimmt man einfach den zuletzt gemerkten freien Block und merkt sich als neuen freien Block, den auf den in dem neu verwendeten verwiesen worden ist. So ersparst du dir auch eine zusätzliche Struktur zur Verwaltung der Blöcke. (In freie Blöcke kannst du ja schreiben was du willst...)

[Dirty Oerti]

Wie meinst du das genau? Reicht es hier aus einen Index in einem Array bzw. einen Zeiger auf die Speicherposition zu haben?

Ein "Index" ist ausreichend, ein Zeiger - da bin ich realistisch - ist bei sowas kaum zu verwirklichen, da bei einer "Kontraktion" ziemlich viele Zeiger umgesetzt werden müssten.
Der Index muss dabei aber auch nicht fortlaufend sein.
Zwar sortiert, aber es kann z.B. die 5 auch fehlen, obwohl die 3 und die 6 belegt sind. Die 5 wird in diesem Fall im Übrigen auch nicht mehr auftauchen. Eine wirklich absolut EINDEUTIGE Identifikation sozusagen.
Das ich nicht auf ein nicht belegtes Objekt zugreife (die 5) ist kein Problem. Das ist geregelt.

Eine Möglichkeit die ich schon öfters gesehen habe, ist es sich den letzten freigewordenen Speicherblock zu merken und wenn ein neuer Speicherblock freigegeben wird die Adresse/Index etc. auf den alten letzten freien Speicherblock in den neuen speichern, um so immer in O(1) einen freien Block zu erhalten. Beim Vergeben nimmt man einfach den zuletzt gemerkten freien Block und merkt sich als neuen freien Block, den auf den in dem neu verwendeten verwiesen worden ist. So ersparst du dir auch eine zusätzliche Struktur zur Verwaltung der Blöcke. (In freie Blöcke kannst du ja schreiben was du willst...)

Das finde ich sehr gut.
Danke schonmal
Mal sehen, in wie weit ich das in mein bestehendes Konzept einpflegen kann.

Wie wäre es mit einer Hashtable?

Wie meinst du das?
Bzw, unter welchem Hintergedanken kommst du auf eine Hashtable?
Eine Hashtable mit Verkettung kann ich ja ausschließen, verkettete Listen aus Objekten gibts nicht.
Ich bräuchte also eine Sondiermethode, um Kollisionen aufzulösen.
Jedoch verschiebe ich das Problem damit nur. Denn: Wie groß mach ich denn meine Hashtable?

Suchen ist für mich ja auch nicht so wichtig.
Wichtig ist, dass ich möglichst wenig Platz verschwende, gleichzeitig aber beliebige viele (zwischen 2 und 20000 o.ä.) Elemente speichern kann. Dabei muss ich möglichst einfach auf die Elemente zugreifen können, weshalb ich eben auf dieses "Quasiarray" gekommen bin.

[Panke]

Was ist überhaupt die Problemstellung?

[Dirty Oerti]

Ich hab eine Menge von Objekten (Sprich Speicherblöcke einer vorgegebenen, festen Größe), die ich verwalten will.
Diese Menge will ich so verwalten, dass ich möglichst wenig Speicherplatz zur Verwaltung verbrate, gleichzeitig ist Geschwindigkeit aber auch verdammt wichtig (eigentlich sogar wichtiger).

Die Anzahl der Objekte variiert stark, sprich von 10 bis hin zu 1000-den.

Zu Grunde liegt mir eine Speicherverwaltung, die 4KB große Blöcke anfordern, oder auch freigeben kann.

Ziel ist es jetzt, dass bei 10 Objekten möglichst z.B. nur 1 Block verwendet werden muss (die Objekte sind selbst immer nur einige Bytes groß), bei vielen dann aber natürlich mehr (aber nur proportional).

Gleichzeitig muss ich 1 bestimmtes Objekt in der Menge (sehr sehr) schnell finden können.

[Panke]

Aber was ist die eigentliche Aufgabe? Ich würde gern den Kontext besser verstehen.

[cloidnerux]

Die Aufgabe scheint es doch zu sein, eine Dynamische Verwaltung für eine Unbestimmte Menge an Objekten zu programmieren. Diese Verwaltung muss schnell und Sparsam sein.
Du hast nur die Möglichkeit 4kb Blöcke anzufragen, sodass einfach für jedes Objekt einen neuen Block anzufragen nicht Funktioniert.
Und das ist egt alles, was ich finde wichtig ist für dieses Problem das es zu Lösen gilt.

[fat-lobyte]

Ich nehme an die Menge sollte nicht "geordnet" sein, also es muss keinen Anfang und kein Ende geben?
Wie siehts denn mit dem Zugriff aus? Fügst du oft objekte ein oder löscht sie? Oder ist das eher etwas das wächst und wächst?
Muss eher das einfügen schnell funktionieren oder der Zugriff?

[Dirty Oerti]

Nein, die Menge ist nicht geordnet, ich brauche nur eine Möglichkeit, jedes einzelne Objekt zu adressieren, z.B. über eine Nummer (die nicht zwingend eindeutig sein muss, aber für die Lebensdauer des Objektes sich nicht ändern darf)

Einfügen und Löschen muss funktionieren, sprich es muss auch so gelöscht werden, dass möglichst nicht eine Situation entsteht, in der z.B. 1000 Objekte nur noch vorhanden sind, die aber auf 1000 4KB Frames verteilt sind. Das wäre sozusagen der Worst-Case

Es wird oft eingefügt und gelöscht, aber nicht annähernd so oft, wie auf die Liste zugegriffen.
Sprich wichtigstes Geschwindigkeitskriterium ist der Zugriff.
Wichtig ist dabei eine Möglichkeit, über die Menge iterieren zu können.