lua-users home
lua-l archive

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

> Just hit me:  What about probing the table only at offsets 2^j to
find an
> upperbound for the actual size?  That takes O(log n) probes.  If you
> you can find tighter upperbounds by a cut-in-the-middle procedure.  Then
> there is no need for any array realloc.

Or do a binary search in the maximum size of an array you are willing to
accept (even if it were 2^32 elements, the binary seach could not take more
than 32 iterations -- but if the typical array size were something like 10,
that would be a waste of cycles. So doing the probe as Wim suggests and
then binary searching between 2^(j-1) and 2^j would get you an exact size
in O(2 * log(actualsize)).

This all assumes that no element of the array is nil. If you could have nil
elements in the array, you really have a problem. (I ran into this with an
app which used nil elements in arrays as spacers, allowing me to do
iterations of array segments.)

You can use the table library to your advantage, though. If you created the
array with table.insert, table.getn would already be set up. If, moreover,
you put an "n" element into the array, it would get updated, so you could
get at it from C:

> a = {n=0}
> for i = 1, 10 do table.insert(a, i) end
> =a.n

This also works if you create the array with a varargs function:

> function array(...)
>> return arg
>> end
> b = array(3, 1, 4, 1, 5, 9)
> =b.n