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

[Tim Hill <drtimhill@...>]

On Oct 6, 2013, at 2:49 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:

> 2013/10/6 Tim Hill <drtimhill@gmail.com>:
> 
>> And in either case, you would still have O(n) performance
> 
> I can think of three possible faster-than-O(n) things you could
> reasonably accept:
> 
> 1. Making # mean the number of active keys of whatever class is O(1) worst-case.
> 2. Making # mean the largest positive integer key you have ever used for this
> table is O(1) worst-case.
> 3. Making # mean the largest positive integer key is O(log(n)) worst-case
> if you are willing to accept an O(n) storage penalty.
> 

I would be interested in seeing a design for 1 or 2 that is O(1).

--Tim