Re: table.maxn...

[Coda Highland <chighland@...>]

On Mon, Jun 1, 2015 at 12:54 PM, Tim Hill <drtimhill@gmail.com> wrote:
>
>> On Jun 1, 2015, at 5:25 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
>>
>> 2015-06-01 12:06 GMT+02:00 Tim Hill <drtimhill@gmail.com>:
>>
>>> 1. Scan the array part of the table (1 to some arbitrary N). If any entry is
>>> nil, return false now; it’s not a sequence.
>>
>> If "some arbitrary N" means "the current size of the array part", N will
>> in current implementation (ltable.c) always be a power of 2 such that
>> at least half the slots are in use.  In other words, up to half the slots
>> may be nil. You can only conclude it is not a sequence if an entry is nil
>> but some later entry is not.
>>
>
> True .. serves me right for posting late at night. It’s a simple fix of course, you walk backwards from the end of the table.
>
> —Tim
>
>

That doesn't help either, because the entry that invalidates the
sequence-ness could be in the hash part. The array part could have 513
values and 511 nils, and the hash part could have an element with a
numeric key of 1025.

You still need to scan it, of course, because if you ever find a nil
in position X and non-nil in position X+1, you can short-circuit and
return false. But you have to scan from one end to the other, so which
end you start from isn't going to make a big difference in practice.
(Stochastically speaking, working backwards is actually slightly
inferior; if the nil that breaks the sequence is randomly distributed
between 1 and the greatest non-nil position, it has greater odds of
being in the first half of the array part than the second half of the
array part, because the first half is guaranteed to be filled but the
second half may only be partially filled.)

/s/ Adam