Re: fast Lua fifo for breadth-first search

[Gaspard Bucher <gaspard@...>]

On Thu, Jan 23, 2014 at 10:12 AM, Valerio Schiavoni <valerio.schiavoni@gmail.com> wrote:

Hello,

On Thu, Jan 23, 2014 at 9:08 AM, Gaspard Bucher <gaspard@teti.ch> wrote:

The ideal solution would be breadth-first search but I cannot see how to implement a fast FIFO in Lua or even in C (do not know how to store a reference to an arbitrary table in a fast way).

There are thousands of available options online to do this. For example:

https://github.com/daurnimator/lomp2/blob/master/fifo.lua

best,

valerio

Thanks for the pointer. I hadn't thought of the "sliding" fifo algorithm. This idea looks nice but I wonder how it scales on large trees. It seems to me that memory allocation for lua tables in such a situation is not that great. But it might also be irrelevant.

I have worked my way into a nice iterative-deepening depth-first search which only tests each node exactly once and does not need to have any stack or fifo. If I find some time and a large enough xml tree, I will do some testing to compare speed of breadth-first search with the fifo you provided and the other algorithm.

G.

--

                                                               Gaspard