Re: Improving the efficiency of next

[Wim Couwenberg <debosberg@...>]

> there seems to be some confusion about the
efficiency of lua_next.

It certainly had me confused a while back!  There are
some subtleties involved with 'next'.  First of all, a
full table iteration takes O(N) where N is the total
number of key/value slots in the table.  However,
consider the following "correct" way to zap a table:

repeat
  local k = next(table)
  if k == nil then break end
  table[k] = nil
until nil

This simple algorithm is *quadratic* in N!  Here's
why:

1.  'table[k] = nil' will *not* change N
2.  'next(table)' is O(N)

In fact, 'next' takes longer and longer to find the
first non-nil entry in 'table'.  The following code to
zap a table is 100% *correct* although it looks
suspicious:

for k in pairs(table) do
  table[k] = nil
end

And, being a full iteration, it takes O(N).  The fact
that this code snippet is correct is one of the
'subtleties' of 'next' (and Lua tables in general) .

--
Wim


__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/