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

[Tim Hill <drtimhill@...>]

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

> Am 06.10.2013 10:00 schröbte Tim Hill:
>> 
>> On Oct 6, 2013, at 12:03 AM, David Heiko Kolf <david@dkolf.de> wrote:
>> 
>>> Dirk Laurie wrote:
>>>> Cheap alternative: Fixed-length table. Length defined once for all. Larger
>>>> indices treated as non-numeric. This may actually cover quite a large
>>>> number of actual use cases
>>> 
>> 
>> @Dirk: "Larger indices treated as non-numeric?" What do you mean?
> 
> I think he means that once a table has a length `n`, even putting a value at `n+1` (or higher) won't change that length.

Yep. I can't see how that is any better (or worse) than either of the other suggestions (using a "maximum" or my "sequence tracker").

>> 
>> And in either case, you would still have O(n) performance hot, which Roberto apparently feels is unacceptable.
> 
> Apparently, he is not the only one: 90% of this thread is about how `O(n)` is not efficient enough for verifying a sequence in a table …

All the suggestions are O(n) at table creation time (actually, mostly are only O(n) for the subset of n where the key is numeric). However, the O(n) argument is mostly spurious since the real, pragmatic issue, is that since table insertion is currently O(n) anyway, what additional overhead (as a percentage) does each need?

Out of curiosity, I patched Lua to support my design (continuous sequence validation), and while I was in the source I tweaked it a bit to optimize Lua performance. Net result was WITH the tweak it ran faster on all the tests I could throw at it than plain Lua. :)

--Tim