[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] Lua 5.2.0 (alpha) now available
- From: Enrico Colombini <erix@...>
- Date: Mon, 13 Dec 2010 09:39:09 +0100
On 13/12/2010 9.29, Dirk Laurie wrote:
The algorithm for #t in ltable.c is (if I read it right):
Consider k, the size of the array part of t. If t has no hash
part and t[k] is not nil, we immediately have #t=k (constant time).
Otherwise either k-1 is an upper bound, or k is a lower bound for #t,
depending whether t[k] is nil. In the latter case, an upper bound
can be found by doubling (logarithmic time). Having an upper and a
lower bound, binary search (logarithmic time) is used to find #t.
So, accessing #t for a mixed table (array + hash) is slower than
accessing it for a pure array with the same data?