|
c't Projekte - c't-Bot und c't-Sim -
Mailinglisten
[Voriger (Datum)]
[Nächster (Datum)]
[Voriger (Thread)]
[Nächster (Thread)]
[Nach Datum][Nach Thread]
Absender: Timo Sandmann
Datum: Fr, 26.09.2008 14:20:42
In-reply-to:
<000001c91f45$9f5e9470$0200a8c0@mexpnew>
References:
<000001c91f45$9f5e9470$0200a8c0@mexpnew>
Hi,
Am 25.09.2008 um 21:33 schrieb Frank Menzel:
Hallo,
habe den Positionsstack etwas erweitert, um diesen als FIFO-Queue
verwenden zu können. Also damit gibt es nicht mehr nur die
Stackfunktionen POP und PUSH sondern auch QUEUE und DEQUEUE um (wie
bei
Push) eine Koordinate hinten anzufügen und vorn wieder zu entnehmen.
das klingt sehr sinnvoll.
Aber warum werden bei der Entnahme eines Elements aus der FIFO alle
anderen darin um eine Position verschoben? Das ist ja sehr
ineffizient. Ich würde eine Datenstruktur mit zwei Zeigern (Indizes)
vorschlagen, einer auf das erste und einer auf das letzte Element, die
dann nur erhöht / erniedrigt werden müssen. Am besten fasst man das
Array dabei als Ring auf, am "Ende" angekommen, springt der jeweilige
Index wieder auf 0. Ist die Arraygröße eine 2er-Potenz, ist diese
Modulo-Operation sehr effizient.
Ich wäre außerdem dafür, keine neue Option "#ifdef POS_QUEUE_FIFO"
einzuführen, sondern wenn der Positionsstack aktiviert ist, dann ist
auch immer die FIFO-Version mit aktiv, das erspart komplizierte
Abhängigkeiten und der Overhead ist minimal.
Grüße,
Timo
|
|