Re: Definition of a sequence

[Andrew Starks <andrew.starks@...>]

On Thu, Jun 11, 2015 at 9:14 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 2015-06-11 10:29 GMT+02:00 Mike <lua-l@inbox.ru>:
>
>> I cannot guess the exact rule for the length operator
>
> The rule is implementation-dependent, but the Lua implementation
> has not recently changed.
>
> In the Lua 5.1 manual, the following boundary property was
> guaranteed:
>
>     t[#t] is not nil, but t[#t+1] is.
>
> This is no longer documented, perhaps because the user can now
> supply a __len that does not have that property.
>
> The implementation does a binary search, once indices i and j
> have been found with the property that i<j, t[i] is not nil, t[j] is nil.
>
> The last index in the "array part" of the table is always the starting
> value for either i or j, with respectively doubling or halving used to find
> the other.
>
> The difference you observe is caused by different sizes of the
> array part.
>
> An implementation change that has been proposed on this list
> is the following: store the previous value of #t and check whether
> it still has the boundary property. This gives O(1) time in the
> common case when the table size has not changed, but
>

It may have been said before, but I found this explanation enlightening. Thanks!

-Andrew