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

[Tim Hill <drtimhill@...>]

On Oct 6, 2013, at 6:05 PM, Philipp Janda <siffiejoe@gmx.net> wrote:

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

Interesting, so it's more or less O(log2(n)). I think I prefer my approach, which had a very small incremental overhead at inserts (so was n * O(1)), but O(1) behavior for #.

--Tim