Absender: Frank Menzel
Datum: Fr, 26.09.2008 19:30:37
In-reply-to:
<A6D9C09A-11AE-4EE7-99D9-D53087213B87@xxxxxxxxxxxxxxx>
Hallo Timo, stimmt natürlich wieder alles. Habe eben "bloß" den vorhandenen Stack, der mittels Array implementiert ist, angepasst um genannte Funktion ohne die Datenstruktur an sich zu ändern. Mittels Zeiger ist natürlich alles viel besser, schöner und effizienter. Das Define kann sicher auch wegfallen, wollte bloß die Trennung verdeutlicht lassen zwischen Stack und Queue und damit Lifo bzw. Fifo. Ist übrigens alles nebenbei angefallen, weil ich das Stackverhalten benutzen wollte aber eben die Daten genau andersrum vorliegen. Also entweder Daten via Push rein und von vorn auslesen und abfahren oder vorn reinschieben und via Pop abfahren. Letzteres hätte den Vorteil, dass das Stackverhalten gleich bleiben könnte. Muss dann aber trotzdem noch modifiziert werden, falls ein Anfahrpunkt doch mittlerweile bei einem Hindernis liegt und zu Beginn der Pfadplanung nicht erkennbar war. Gruß, Frank -----Ursprüngliche Nachricht----- Von: ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx [mailto:ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx] Im Auftrag von Timo Sandmann Gesendet: Freitag, 26. September 2008 14:21 An: Entwicklung rund um den c't-bot Betreff: Re: [ct-bot] Erweiterung Posstack als FIFO-Queue 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 _______________________________________________ ct-bot-entwickler Mailingliste ct-bot-entwickler@xxxxxxxxxxxxxxxxx http://www.heise.de/bin/newsletter/listinfo/ct-bot-entwickler