Re: pairs(t, skey) and ipairs(t, skey)

[Philipp Janda <siffiejoe@...>]

Am 07.10.2013 02:37 schröbte Tim Hill:
> i think we're saying the same thing from a different viewpoint ..
> there is a certain amount of work to be done, and it can either be
> done late (at # time, with O(n) cost) or early (at insert time, with
> n * O(1) cost). Both have (well known) trade-offs of course.

Exactly.

> I have not looked at the code in detail, but I suspect the current #
> behavior is more or less a "freebie" side-effect of how the table
> internals work, hence it's odd behavior with non-sequence tables.

Not really. The current code basically works like this:
*   If there is a nil at the end of the array part, use a binary search 
to find a (non-nil,nil) pair in the array part -> that's the length.
*   Otherwise use the size of the array part as a starting point, and 
look for a nil entry in the table, doubling the position where you look 
at every step. When you find a nil entry, do a binary search between 
this entry and the last position you looked (which was non-nil) to find 
a (non-nil,nil) pair -> that's the length.

Using binary search to find *any* (non-nil,nil) pair (instead of the one 
with the smallest index) avoids linear complexity.

> --Tim

Philipp