|
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: 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
|
|