Re: 5.2 work3 manual

[Florian Weimer <fw@...>]

* Tony Finch:

> On Wed, 19 May 2010, Gavin Wraith wrote:
>>
>> Postscript. In view of the troubles with holes, one might prefer
>> to deal with arrays of non-nil values. So a table x is an Array (to
>> distinguish from any previous notion) if either it is {} or
>> there is a positive integer n such that x[i] is non-nil for
>> i = 1, ... ,n and is nil for all other keys. For such a table I
>> presume that #x = n. Then the Array-part of a table t is an Array x
>> for which (t[i] and x[i] and t[i] == x[i]) is true for all i = 1, ... ,n.
>
> Your definition requires an O(n) search to evaluate #x, whereas Lua's
> definition allows an O(log n) search.

Not really, you could use balanced binary trees or Judy trees, which
would bring you down to O(log n).  On the other hand, I'm sure that
the constants would be far worse than the current implementation.