lua tree structure questions..

[smoth]

How expensive are recursive tree traversals in lua?
Do we have something like a linked list or tree structure we can use?

I am only aware of tables and table operations in lua, just wondering what other kind of things we have. I know we could nest tables in tables, is that how I can do hierarchical data in lua? Is it expensive for lua to traverse said structure?

[FLOZi]

Everything else is built with tables.

As for expense... build it and find out? Otherwise I'd get in #lua and ask jk.

I can predict the first question; What do you want to build and why?

[Kloot]

Do we have something like a linked list or tree structure we can use?

No, any such structures have to be built out of tables.

I am only aware of tables and table operations in lua, just wondering what other kind of things we have.

none

I know we could nest tables in tables, is that how I can do hierarchical data in lua?

yes

How expensive are recursive tree traversals in lua?

For iterative traversals: C = L * S
For recursive traversals: C = (L + F) * S

where

L is the cost of a Lua table lookup
F is the cost of a Lua function call
S is the size of the structure you have in mind
C is a rough indication of cost in your favorite unit of currency

Is it expensive for lua to traverse said structure?

That depends on how much money you have and how much you are willing to spend.

[smoth]

Well I was more wondering if recursion is MORE expensive in lua than say C++ sort of a relative thing.

I don't understand much about the internals but you know stuff like how POW calls are/were expensive in C++. I forget all the reasoning behind it but there was a good reason to use other ways like just doing a loop multiply etc.. this was a long time ago so this may not be true any more or was just an issue with hardware..

anyway, just because I can do something doesn't mean I should.. if you get me.

[Tobi]

Lua has guaranteed tail call optimization (TCO).

So if you can write your recursion in a way where the calling function doesn't need to do anything with the result of the called function except return it, then the recursion doesn't use any stack space (it's just like a goto then).

Silly example where TCO is applicable:

Code: Select all

function f(n)
  if n > 0 then return f(n - 1) else return 1 end
end

Silly example where TCO is not applicable:

Code: Select all

function f(n)
  if n > 0 then return n * f(n - 1) else return 1 end
end

If you don't see why then don't rely on it