BenBE - Mi 13.05.09 12:26
Titel: Round Robin in großen Bitfeldern

---

Irgendwo häng ich grad ein wenig.

Ich habe ein Bitfeld, welches NICHT in ein Register passt (4*32*32*3 Einträge), wobei es eine Hierarchische Ordnung gibt, um gesetzte Bits schneller zu lokalisieren. d.h. jeder Bitfeld kann als Knoten in einem Baum aufgefasst werden, welches angibt, welche Kindknoten existieren. Im Speicher gibt es dazu aber nur 4 Arrays: Für jede Ebene eines.

Also wenn in Knoten 2-0-3 Eintrag 1 gesetzt ist, sieht das etwa so aus (weitere Einträge sind vorhanden):



Speichertechnisch liegt Ebene 4 als 3 Bitsets vor, aus denen Ebene 3 dynamisch generiert wird. Die Priorität funktioniert dort aber ähnlich.

Was ich nun suche ist eine elegente Möglichkeit, dass wenn mehrere Bits gesetzt sind, ich bestimmte (niederwertige Bits) ignorieren kann, um immer in einem Zyklus durchzugehen... D.h. dass wenn der letzte Eintrag, der gelesen wurde aus dem Bitfeld, Eintrag 2-1-0-1 war, mindestens 2-1-0-2 folgen muss, selbst wenn auch 0-0-0-0 gesetzt wäre (sei denn, dort gibt es keinen gesetzten Eintrag mehr, dann von vorne). Irgendwo häng ich da mit der Logik grad ...

Zum Lesen der Bitfelder hab ich Funktionen, die immer das LSB, liefern, bzw. mir Bitmasken generieren. For-Schleifen sind IMHO nicht nötig, daher zu vermeiden.

Soweit ich das überblicke, müsste das in Linearzeit möglich sein.

Bisher hab ich aber leider nur den Ansatz für den ersten Eintrag der Liste (im obigen Beispiel also laut Beispiel 2-0-3-1. Wäre 2-0-0-0 gesetzt, würde mir der folgende Algo diesen Liefern (wenn die Leseposition aber 2-0-3-0 anzeigt, darf frühstens dieser auftauchen).

Hier mal ein Beispiel für das Lesen (des frühsten) möglichen (unabhängig vom Lesezeiger):


Wo ich jetzt nicht weiterkomme ist, wie ich welche Bits vorübergehend ausblenden muss, damit ich die Positionsanzeige korrekt erhalte. data darf nicht verändert werden.

Bin über jegliche Tipps dankbar.

Bei Alternativvorschlägen: Müssen konstanten Speicherverbrauch haben UND echtzeitfähig sein.

Thorsten83 - Mi 13.05.09 15:58

---

Bin mir gerade nicht ganz sicher ob ich das Problem richtig verstanden habe, ich fass es mal zusammen:

In der untersten Ebene stehen die Bits, die dich interessieren (12288 Stück)
Die Ebene darüber hat weniger Bits (4096), jedes davon bedeutet, dass von den 3 darunter liegenden Bits eines gesetzt ist, oder nicht (Also bits[n] = bits[3*n] | bits[3*n + 1] | bits[3*n + 2]).

Du willst jetzt durchgehen, und rausfinden, welche Bits der unteren Ebene gesetzt sind?

BenBE - Mi 13.05.09 18:22

---

Könnte man grob so umschreiben, wobei ich nicht ein beliebiges Bit herausfinden will von der ersten Ebene, sondern das erste Bit links (oder gleich) dem Bitzeiger. (Wibei die Anzahl Bits und die Struktur konfigurierbar ist in gewissen Maßen, das Layout sieht nur etw so aus).

Nehmen wir einfach mal an, unser Bitfeld wäre etwas kleiner (Pro Ebene nur jeweils 2 Bit:



d.h. Bit 2 und 5 sind derzeit gesetzt. Wie kann ich nun möglichst effizient das nächste Bit herausfinden, wenn der aktuelle Zeiger auf Bit 3 steht (Korrekte Antwort des Algo muss Bit 5 sein)?

(Allgemein: Das Bit mit der kleinsten Bitnummer >= Zeigerposition)

uall@ogc - Mi 13.05.09 22:29

---

Einfacher inorder Durchlauf.

Wenn du bei Bit 3 bist alle in der ebene links davon verarbeiten und schaun ob 1, wenn nciht ebene höher und dort durchgehen Bis 1. falls icht gefunden wieder höher usw. wenn gefunden wieder wurzel verarbeiten etc.

Thorsten83 - Do 14.05.09 01:08

---

uall@ogc hat folgendes geschrieben :

Einfacher inorder Durchlauf. Wenn du bei Bit 3 bist alle in der ebene links davon verarbeiten und schaun ob 1, wenn nciht ebene höher und dort durchgehen Bis 1. falls icht gefunden wieder höher usw. wenn gefunden wieder wurzel verarbeiten etc.

Ist eine Lösung, funktioniert aber nur, wenn es ausreicht, eine Liste mit den abzuarbeitenden Bits zu erstellen.
Alternativ einfach eine Warteschlange?
Ich gehe mal davon aus, dass die Anzahl der 1-Bits relativ gering ist, sonst würdest du das wohl kaum so aufwendig machen, oder?
Vorteil: enqueue/dequeue in O(1), Speicherbedarf O(n).

Ansonsten ist halt auch die Frage: was passiert, wenn du das nächste 1-Bit suchst, aber keines findest? Durchläufst du den Baum immer wieder? Sowas kann eine SPS z.B. zum Abschmieren bringen, wenn die neuen Daten nicht per Interrupt reinkommen...

BenBE - Fr 15.05.09 09:49

---

Regelfall ist durchaus, dass nur sehr wenige Bits gesetzt werden. Sind keine Bits gesetzt, lässt sich dies direkt in der obersten Ebene abfangen.

Ganz O(n) ist der Speicherbedarf durch die Baumstruktur nicht; würde das eher als "zwischen O(n) und O(n*log(n))" beschreiben.

Derzeit hab ich erstmal eine Lösung umgesetzt, die statt einem Overflow nur die Positionsänderung bewirkt, sonst aber kein Element unqueued. Das ist für meinen Fall durchaus auch akzeptabel.

Wo ich aber noch unsicher bin ist die Frage bzgl. dem "Ebene hoch und nächstes Element" inwiefern man da u.U. Code sparen kann, so dass man nicht alle 15 Cases vollständig ausprogrammieren muss (Case 16 ist "kein Bit gesetzt").

@Baum-Traversierung: Ja, derzeit schon. Daher such ich ja eine Effiziente Lösung, mit der ich das auf ein Minimum beschränken kann.