Re: Proposal for table length operator

[Keith Matthews <keith.l.matthews@...>]

> 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.
>
> 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 believe you meant "the largest, 1000")

Actually, table.remove will call lua_objlen() to get the table size
(1000 under my proposal), and will remove it immediately. Under my
proposal, removing the last element is always O(1). In Lua 5.1, I
think it is somewhere between constant and linear time, depending on
the table contents, and it would fail to remove anything in this
particular case.

If you had called table.remove(t, 1), it would have been O(n), and
every item index would have been shifted down. In Lua 5.1, it would
have taken no time and would have done nothing.

> 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.

Of course, if you need to sort, you can't put nil in the array. I
don't expect my proposal to change that. It already works like this in
Lua:

> t = {4, nil, 3, 2, 1}
> table.sort(t)
-> attempt to compare nil with number

If #t were the number of non-nil element from the start of the array,
table.sort would succeed, and the table would be unchanged.

The fact that the table implementation has an array part and a hash
table part is an implementation detail. It shouldn't prevent using the
table as the programmer sees fit.

- Keith