lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

>Yes, but its performance is awful on large tables. It is basically
quadratic in table size.

Um, this statement implies that next(table, nil) is linear in table size.
Is the implementation of next really written in such a horrendous way?

(I'll check the code later if necessary.)
The "obvious" implementation to me would result in next(table, nil) having
constant time, and other cases of next being bounded by a standard Lua table
lookup process (with a quick internal adjustment to move to the next hash
table entry).
Hmm, IIRC there were some complaints about next using a global variable (via
rawset/rawget), which causes problems for sandboxing.  If that is correct
then my assumption about the "obvious" implementation must be off (probably
this was done to get constant time for next in all cases).
(So, again I say I'll check the code later if necessary.)

>Actually, I don't think your code handles a table with the key false.

That's why I included the comments...
-- OK, lookup type checking to
-- ensure nil rather than false
I just didn't take the time to work out the proper type check.
So what I intended was....

   key = next(table, nil)
   if (type(key) ~= "nil") then
      table[key] = nil
until (type(key) == "nil")

But your "for implementation" is more concise, however, I think it was twice
as long as needed.  The following should be fine (I think), however, this is
a bit sneaky in that its "abusing" parameter matching to pass nil to next.
for key in next, table do table[key] = nil end