[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Improving the efficiency of next**
**From**: Wim Couwenberg <debosberg@...>
**Date**: Thu, 27 Nov 2003 02:39:56 -0800 (PST)

> 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/