lua-users home
lua-l archive

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


> Nope, it's a binary search for an item followed by a nil:
> http://www.lua.org/source/5.2/ltable.c.html#luaH_getn
> In the worst case, it's a linear search.

This linear search is not a typical "worst case". It can only happen if
you build your table in a very meticulous way explicitly to have a bad
behavior. It is even more difficult to build a table that both need the
linear search and where this search traverses many elements. (Try it.
Hint: your table must have a numeric key larger than MAXINTEGER/2.)

For all practical considerations, the search is always a binary search.

-- Roberto