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

[Tim Hill <drtimhill@...>]

On Oct 6, 2013, at 4:49 AM, Philipp Janda <siffiejoe@gmx.net> wrote:

> Am 06.10.2013 12:48 schröbte Tim Hill:
>> 
>> 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).
> 
> 1.)
>    * add a counter to the table structure
>    * increment the counter whenever you add a new non-nil value to the table, or when you replace a nil-value with a non-nil value
>    * decrement the counter whenever you set a non-nil value to nil
>    * `#` returns the counter
> 
> 2.)
>    * add a field largest_known_integer_key_so_far to the table structure
>    * whenever you add an integer key that is bigger than the largest_known_integer_so_key_far, update that field
>    * `#` returns largest_known_integer_key_so_far
> 
> Both approaches have O(1) memory and runtime overhead for `#` and for table insertion.
> 
> Am I missing something?
> 

Both are O(n) execution time (we're not talking about memory overhead).

--Tim