C
Cal
Gast
Hey,
ich habe mal wieder ein größeres Problem. Ich möchte eine Untidy Priority Queue (wie sie im Fast Marching Algorithmus verwendet wird) schreiben.
Dieser Datentyp verhält sich ähnlich wie eine Priority Queue, nur dass er in O(1) einfügen und entfernen kann, wofür eine Priority Queue O(log n) benötigt, dafür nimmt er einen kleinen Fehler bei der Sortierung der Elemente in Kauf. Ausserdem geht er von einem monotonen Einfügeverhalten aus: Jedes Neueingefügte Element ist mindestens so groß wie das letze welches gezogen wurde.
genaueres gibt es in diesem Paper auf Seite 3: http://mountains.ece.umn.edu/~liron/fastmarching/O_N_fast_marching.pdf
Im Prinzip funktioniert sie so:
Ein zyklisches Array beinhaltet an jeder ArrayPosition eine Liste von Elementen (jeweils mit einem key, nach dem sie sortiert werden können) Jedes Bucket von diesem Array enthält nur Elemente mit ähnlichem key (bzw einem Key>Tn und Key<Tn+1) Das Bucket mit den kleinsten Werten wird T0 bezeichnet. Auf T0 wird ein Verweis abgespeichert, damit man das kleinste Bucket kennt. Wenn alle Elemente aus dem niedrigsten Bucket entfern wurden, wird der Verweis einfach aufs nächsthöhere Bucket gelegt.
Einfügen: der Key k soll hinzugefügt werden. Das Bucket kann einfach durch Math.Floor((k-T0)/delta) - T0 ist der mindestWert für das kleinste bucket - gefunden werden -> O(1)
Poll: einfach den ersten key aus dem T0 bucket holen -> O(1)
Nun mein problem: Die Remove Operation. Die Autoren des Papers behaupten das gehe in O(anzahl der buckets), nur wie?
naja...wenn ihr Zeit habt guckt mal in das Paper rein, vlt könnt ihr mir ja weiterhelfen
Gruß
Cal
ich habe mal wieder ein größeres Problem. Ich möchte eine Untidy Priority Queue (wie sie im Fast Marching Algorithmus verwendet wird) schreiben.
Dieser Datentyp verhält sich ähnlich wie eine Priority Queue, nur dass er in O(1) einfügen und entfernen kann, wofür eine Priority Queue O(log n) benötigt, dafür nimmt er einen kleinen Fehler bei der Sortierung der Elemente in Kauf. Ausserdem geht er von einem monotonen Einfügeverhalten aus: Jedes Neueingefügte Element ist mindestens so groß wie das letze welches gezogen wurde.
genaueres gibt es in diesem Paper auf Seite 3: http://mountains.ece.umn.edu/~liron/fastmarching/O_N_fast_marching.pdf
Im Prinzip funktioniert sie so:
Ein zyklisches Array beinhaltet an jeder ArrayPosition eine Liste von Elementen (jeweils mit einem key, nach dem sie sortiert werden können) Jedes Bucket von diesem Array enthält nur Elemente mit ähnlichem key (bzw einem Key>Tn und Key<Tn+1) Das Bucket mit den kleinsten Werten wird T0 bezeichnet. Auf T0 wird ein Verweis abgespeichert, damit man das kleinste Bucket kennt. Wenn alle Elemente aus dem niedrigsten Bucket entfern wurden, wird der Verweis einfach aufs nächsthöhere Bucket gelegt.
Einfügen: der Key k soll hinzugefügt werden. Das Bucket kann einfach durch Math.Floor((k-T0)/delta) - T0 ist der mindestWert für das kleinste bucket - gefunden werden -> O(1)
Poll: einfach den ersten key aus dem T0 bucket holen -> O(1)
Nun mein problem: Die Remove Operation. Die Autoren des Papers behaupten das gehe in O(anzahl der buckets), nur wie?
naja...wenn ihr Zeit habt guckt mal in das Paper rein, vlt könnt ihr mir ja weiterhelfen
Gruß
Cal
