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

[Coda Highland <chighland@...>]

On Sun, Oct 6, 2013 at 10:54 AM, Tim Hill <drtimhill@gmail.com> wrote:
>
> 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

Algorithmically speaking, both approaches are O(1) per access on top
of whatever algorithmic complexity the underlying implementation has.
It has no impact on the algorithmic complexity of any algorithm that
the change is applied to.

/s/ Adam