lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


t[#t] = nil works for strict linear arrays only. Since when t[1] ==
nil, #t can be 0 or might not be 0.

As far I understood this proposal table.remove(t) has O(n) costs.
Since

t[500] = 1
t[750] = 1
t[1000] = 1
table.remove(t)
now it has to scan all values to find the largest, 750.

I think anyway in some way "largest" and "smallest" always require
some sorting at some point and thus conflict with the idea of the
hashtable as efficient unsorted data. IMHO #t as number of elements
that are not nil would be the sensible thing to be. Altough that way
it can neither be used to append or cut from the end - which you
shouldn't do from a hashtable anyway, without assigning the numbers
right away.

I suppose beside this reason they didnt want to have a n counter for
tables. Maybe I should study the table implementation for Lua, but
dont have hash tables an n counter anyway? How do you know when to
rehash without?


On Tue, Dec 14, 2010 at 9:14 AM, Enrico Colombini <erix@erix.it> wrote:
> On 14/12/2010 5.03, Keith Matthews wrote:
>>
>> So here's yet another proposal for the table length operator. It is
>> simple to understand, simple to implement, useful, and with a low
>> algorithmic cost (i.e. O(1) to update or to query the length of a
>> table.) Even better, arrays with holes and sparse arrays would not be
>> a special case anymore.
>
> I find this proposal interesting (it also has the added advantage of
> increasing performance); its main problem, as you note, is the amount of
> code that would break because of "t[#t] = nil".
>
> --
>  Enrico
>
>