Re: Lua Basics: tables as lists?
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Lua Basics: tables as lists?
- From: Rici Lake <lua@...>
- Date: 2005年8月22日 22:50:35 -0500
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