Re: Speed of #t

[Axel Kittenberger <axkibe@...>]

Well IMHO it should return 7 then, yes it will have to traverse it if
there is a long table followed by it.

just for curiosity. What does currently happen if you insert a nil in
an array? It will stay an array and not turn the tail into a hash
right?

t[1] = 1; t[2]=2; t[3] = 3
will result into quite another internal data structure than
t[3] = 3; t[2]=2; t[1]=1
?

One possibility of staying with O(1) and having a more meaningful #
would be to internally save the length of every continous integer part
in a hash table at the beginning of the chunk
1   a   (# is 3)
2   b
3   c
4   nil
5 d (# at 5 is 2)
6 e
..7 nil..

so if you set 4=x, it can add 3 + 2 + 1.

Altough it maintains a O(1) its supposevly not so efficient in
everyday cases tough,

On Mon, Dec 13, 2010 at 1:10 PM, David Kastrup <dak@gnu.org> wrote:
> Enrico Colombini <erix@erix.it> writes:
>
>> On 13/12/2010 11.14, Axel Kittenberger wrote:
>>> Likely I'm a bit naive about this. But couldn't we just define for #
>>> operator to simply return the size of the array part?
>>>
>>> Meaning counted from 1 onwards # to defined the the largest numeric
>>> key where t[k] is not nil. t[#t+1] is nil.
>>
>> I'd be happy with that, but (apart from other people having different
>> wishes) consider what will happen if you have a table such as:
>>
>>  t = { 1, 2, 3, nil, 5, 6, 7, ... } -- a very very large table
>>
>> #t would be 3.
>> Now fill the hole:
>>
>>  t[4] = 4
>>
>> To update #t correctly according to your definition, all the remaining
>> length of the array would probably have to be traversed sequentially.
>
> Why? t[4] = 4 will presumably just increase the array part by one,
> resulting in #t == 4.
>
> --
> David Kastrup
>
>
>