Re: fast Lua fifo for breadth-first search

2014/1/23 Gaspard Bucher <gaspard@teti.ch>:

> I am working on a fast xml library (using RapidXML) and want to implement a
> simple search algorithm to find the first node with a given tag.
>
> From my own extensive use of such 'find' functions, the objects to find are
> usually near the surface so I want to avoid depth-first search.

Two thoughts:

1. Do you mean "first" according to some definition of precedence or "any"?
2. In either case, the overhead in creating a Lua table by tag (values being
nodes or arrays of nodes) may be compensated by Lua's fast hashtable
searching.

The library will find first or any depending on the callback function passed. It can be used as a find, collect or traverse.

I did some testing and the fastest solution depends on whether we use Lua or LuaJIT.

Results:

===== Lua

1. IDDFS 5.10

2. BFS - raw test 2.42

3. BFS 2.58

4. BFS - no depth test 2.09

===== LuaJIT

1. IDDFS 0.30

2. BFS - raw test 0.35

3. BFS 0.36

4. BFS - no depth test 0.33

The nice thing is that:

Using raw testing (2) instead of using a function call does not imply any huge difference in speed.

Depth testing (4) does not have too much impact (and is so much better then just hanging on a graph loop).

The surprise:

IDDFS has very different speed results with Lua and LuaJIT. My 2c guess here is that it's the only recursive algorithm and Lua does not optimize function calls as well as LuaJIT.

==== CODE USED

Here is the BFS algorithm. I really like how Lua translates well from theory to implementation when working with algorithms. Apart from the fifo code, this looks very close to pseudo-code...

--------- BFS

function BFS(data, func, max_depth)

max_depth = max_depth or 10000

local queue = {}

local depth = {} -- depth queue

local head = 1

local tail = 1

local function push(e, d)

queue[tail] = e

depth[tail] = d

tail = tail + 1

end

local function pop()

if head == tail then return nil end

local e, d = queue[head], depth[head]

head = head + 1

return e, d

end

local elem = data

local d = 1

while elem and d <= max_depth do

local r = func(elem)

if r then return elem end

for _, child in ipairs(elem) do

if type(child) == 'table' then

push(child, d + 1)

end

elem, d = pop()

end

--------- IDDFS

local function itdeepSearch(data, func, depth, max_depth)

local end_reached = true

local result

for _, child in ipairs(data) do

if type(child) == 'table' then

if depth == max_depth then

local r = func(child)

if r then

return r

elseif child[1] then

-- Could search deeper

end_reached = false

end

elseif child[1] then

-- Go deeper

local r, e = itdeepSearch(child, func, depth + 1, max_depth)

if r then

return r

else

end_reached = end_reached and e

end

return nil, end_reached

end

function IDDFS(data, func, max_depth)

local depth = 1

max_depth = max_depth or 10000

local r = func(data)

if r then return r end

while true do

local result, end_reached = itdeepSearch(data, func, 1, depth)

if result then

return result

elseif end_reached then

return nil

elseif depth < max_depth then

depth = depth + 1

else

return nil

end

--

Gaspard