lua-users home
lua-l archive

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

--- In, "Wim Couwenberg" <w.couwenberg@c...> wrote:
> Hi again...
> > The table doubling trick that I mentioned at the end of my mail is
> > 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
> you can find tighter upperbounds by a cut-in-the-middle procedure.  Then
> there is no need for any array realloc.

These are all perfectly valid/cheap/etc. solutions. But I doubt that
they would be worth it in my case as the problem is not so much the
performance. It's just that iterating twice over the table didn't seem
sensible so I thought I might be overlooking a better solution(since
I'm new to lua) so I asked. Thanks for posting though.