Lücken in Zahlenreihen finden
-
Aktuell vergebe ich an manchen Stellen ID's. Das mach ich momentan ganz stupide mit 64 bit werden die ich einfach hochzähle. Durch löschen einzelner Werte können dabei Lücken entstehen. Diese würde ich ggf gerne wieder befüllen. Welche Ansätze kann man da verfolgen ohne einfach bei jeden insert zu schauen wo denn da eine Lücke ist? Ich könnte z.B. 10,100 oder 1000 id's vorrätig haben die noch nicht vergeben sind. Und erst wieder neue generieren wenn dieser Vorrat erschöpft ist. Aber das verschiebt eigentlich nur den Zeitpunkt des durchzählens. Gibts ggf bessere Ansätze?
-
Fedaykin schrieb:
Diese würde ich ggf gerne wieder befüllen.
Warum? Befürchtest du ernsthaft, dass dir sonst die IDs ausgehen?
Im Allgemeinen ist das eine sehr schlechte Idee. Wenn du so etwas tust, musst du penibel auf referentielle Integrität achten, damit nicht irgendwann zwei Datensätze verknüpft werden, die nichts miteinander zu tun haben.
Kurz gesagt: Lass es.
-
Eine Liste aller freien IDs vielleicht.
Oder Du gehst von vorne bis hinten alle durch und prüfst, ob sie vergeben ist.
-
Da hat sich mal jemand ziemlich viele Gedanken zu gemacht:
http://labs.trolltech.com/blogs/2008/10/22/a-never-ending-struggle/
Da gehts zwar um 32 Bit signed IDs aber ich denke die Idee ist klar.
Bei 64 Bit so ein Verfahren zu implementieren ist aber totaler Schwachsinn. Der Speicherverbrauch und Aufwand ist gigantisch.
Ich glaube dir ist auch nicht ganz klar was 64 unsigned Bit bedeutet:- Wenn du jede ms(!) eine ID vergibst kannst du das für fast 600 (!!) Millionen (!!!) Jahre (!!!!) machen bevor dir die IDs ausgehen.
- Wenn im Durchschnitt die Hälfte der IDs belegt sind bräuchtest du 33 Millionen Terabyte Speicher, nur für die IDs.
Wenn du deinen ID Datentyp von vornherein richtig wählst wirst du niemals in das Problem von zu wenig IDs laufen. Falls du jetzt noch nicht genau abschätzen kannst wie sich die Anforderungen in Zukunft entwickeln kannst du Problemen durch gutes Design entgegensteuern (in C++ z.B. typedefs).
-
Also ich habe für ein Programm von mir ein recht ähnliches System (bei mir sind die Indizes tatsächlich knapp!), welches ganz gut funktioniert. Man sollte vielleicht noch sagen, dass bei mir das Verhältnis Lücke zu Belegt eher klein ist. Wenn das System mehr Lücken als Belegung hat, würde ich vielleicht was anderes machen. Es ist schlicht eine Liste mit freigewordenen Indizes, aber ohne die Indizes die hinten noch nie belegt wurden. Wenn die Liste leer sein sollte wird hinten angehängt, ansonsten wird ein Index (der Erste, aber das ist egal) aus der Liste genommen und dieser benutzt.
Ja, auf die Verknüpfung von Datensätzen muss man genau achten. Ich hatte in der Praxis jedoch kein Problem damit, weil bei den Aktionen die zum freiwerden eines Indexes führen (also das Löschen) ohnehin schon die Integrität der Daten sichergestellt wird, indem entsprechende Querverweise gelöscht werden. Dies funktioniert natürlich nur, solange das System für sich abgeschlossen bleibt (was bei mir der Fall ist), falls externe Verweise auf einen Index existieren bricht das ganze System zusammen.
-
Das Problem ist ja nicht das mir die ID's ausgehen könnten. Sondern das ich eigentlich kein 64 Bit Wert verwenden will.
Ich gehe mal davon aus das mir eigentlich 16 Bit reichen würden. Da ich davon ausgehe das ich nicht mehr aus 65000 Objekte des gleichen Types habe. Das Problem ist dort aber eben jenes mit den lücken.
Das was bei mir im System eben knapp ist, ist der Speicher. Wenn ich also was in 64 Bit speichern muss was ich auch in 16 unterkriegen würde, ist das eher schlecht. Daher die Frage mit der Lückenfindung, ich schau mir mal den Link von rean an.
-
wenn die IDs sich ändern dürfen, dann wirf immer die letzte weg
-
Das was bei mir im System eben knapp ist
Dann solltest du mal mehr Infos ueber dein Zielsystem herausruecken. Willst du die Luecken fuellen, so muessen IDs, oder die Objekte, zentral zugaenglich sein. D.h. du musst die vergebenen IDs speichern oder aber alle Objekte in eine Liste packen, um spaeter die IDs abzurufen. Ok, vergebene ID speichern kostet 16 Bit + Overhead des Managers + Overhead einer Liste, der sie verwaltet. Zeiger auf Objekte kostet 32 Bit (also auf einem 32 Bit System) + Overhead fuer die Verwaltung. Entscheide selbst ..
-
Das wirkliche Zielsystem ist nicht bekannt. Dummerweise nicht die Beschränkung auf "Wenig Speicherverbrauch" Genau deswegen muss ich die ID's einführen. Es ist eine art Load On Demand Lösung.
Da die Objekte auch untereinander Referenzieren, aber nicht sichergestellt ist, dass sich diese in gleichen Streams befinden müssen die ID's eingeführt werden. Und damit fingen die Probleme an. Angefangen bei: "Wie bestimmte ich die ID's eindeutig ohne das Alle Objekte geladen sind". Bis zu: "Was mache ich mit ID's die auf einmal nirgendswo mehr drauf referenzieren."
Vieles davon kann ich mehr oder weniger Effizient lösen. Ob ich das mit dem ID Recycling wirklich lösen kann weiss ich noch nicht.
Ist eh dumm wenn man auflagen kriegt wie: "Wenig speicher dafür schnell und effizient" das schließt sich gegenseitig aus.
-
Wenn es dir um Speicherverbrauch geht und du davon ausgehst dass dir 2^16 IDs reichen würde sich ein Bitset lohnen.
Für ein Bitset bräuchtest du bei 2^16 IDs 8 kB Speicher.
Wenn im Durchschnitt ein Großteil deiner IDs belegt sind würde es Sinn machen die nicht belegten zu speichern.
Ab spätestens 4096 Einträgen ist dein Container größer als das Bitset. Das entspricht 6,25% aller möglichen IDs.
Dir stehen drei Container zur Auswahl: Baum, Listen, Array von Arrays (Deque).
Gehen wir mal davon aus dass beim Baum jeder Knoten zwei 16Bit Verweise hat (Eigene Implementierung, links, rechts), damit sinkt der Prozentsatz für nen Baum auf ca. 2.
Ne Liste würde mit einem Verweis auskommen, hätte also nen Prozentsatz von ca. 3.
Deque hätte vielleicht so um die 5%.
Die Überlegungen für den Umgekehrten Fall, im Durchschnitt sind die meisten IDs unbelegt, überlass ich dir.
Mit anderen Worten: Ein Bitset würde sich für deinen Anwendungsfall lohnen sobald du im Durchschnitt zwischen 2000 und 63500 IDs hast.Die Suche in nem Bitset ist auf alle Fälle schneller als in einer Liste und je nachdem wie geschickt mans implementiert unwesentlich langsamer als in nem Baum.
Ich würde also zu ner eigenen Bitset-Implementierung raten.
-
Hi,
mach nen Stapel der friegegebenen IDs und sieh bei der Neuvergabe erst darauf nach, ob da noch was drauf ist und erst wenn der Stapel leer ist nimm ne frische aus dem ID-Pool.
Alternativ, wenn Du genau weist, wo jede ID verwendet wird, dann nimm beim Löschen einer ID die als neuen Wert für die letzte ID und gib die letzte frei.Gruß Mümmel
