lua-users home
lua-l archive

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

Hi again...

> The table doubling trick that I mentioned at the end of my mail is both
> simple to implement and totally acceptable (its cost may depend a bit on
> what you actually store in your array of course.)

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 want
you can find tighter upperbounds by a cut-in-the-middle procedure.  Then
there is no need for any array realloc.