Re: Lua Basics: tables as lists?

[Rici Lake <lua@...>]

On 22-Aug-05, at 9:52 PM, William Trenker wrote:

> It's easy to set up lua lists:
> mylist = {"a", "b", "c"}
> What I'm wondering is what is the design-intended best practice for
> testing for list membership.  And what is the fastest way to do this?

If you don't actually care about the order of the objects (which is a 
surprisingly common case), then do it like this:

myset = {a = true, b = true, c = true}

-- is an object in the set?
  if myset[obj] then ...

-- get all the objects out of the set (in undetermined order):
  for k in pairs(myset) do ...

Note that you cannot add objects to the set during the iteration, which 
is a bit annoying if you're doing a workqueue. However, you can fake it 
by using three sets.

This assumes that we're storing a digraph as a table of sets, such that
digraph[node_a][node_b] is true if there is a line node_a -> node_b.
Then the following function computes the set of nodes reachable from a 
given node.
It may not be the fastest way of doing it, but it seemed like a simple 
example:

function reachable(digraph, node)
  local empty = {}
  local done, work, pending = {}, {}, {}
  local function insert(stateset)
    if not done[stateset] then
      done[stateset], pending[stateset] = true, true
    end
  end

  insert(node)

  repeat
    pending, work = {}, pending
    for node in pairs(work) do
      for next_node in pairs(digraph[node] or empty) do
        insert(next_node)
      end
    end
  until not next(pending)

  return done
end

("not next(pending)" is true if pending is empty, assuming that false 
is not a possible key. If false were possibly you'd have to say "until 
nil == next(pending)", which would be more readable but slightly 
slower.)


> Assuming that for-loops are run-time expensive for large lists, is
> something like this considered good practice?

For loops are not expensive

> myList = {"a", "b", "cde"}
> myListString = "|" .. table.concat(myList, "|") .. "|"
> a = "cde"
> if string.find(myListString, "|"..a.."|") then
>     print("found!")
> else
>     print("not found")
> end

That is very expensive