Zum Inhalt
c't

c't Projekte - c't-Bot und c't-Sim - Mailinglisten

c't-Bot und c't-Sim


[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

Re: [ct-bot] Erweiterung Posstack als FIFO-Queue

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