[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Why do we have ipairs?**
**From**: Roberto Ierusalimschy <roberto@...>
**Date**: Tue, 10 Jun 2014 14:11:30 -0300

> 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