lua-users home
lua-l archive

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

On 2016-08-18 19:20, Ross Berteig wrote:
> Honestly, the cost of writing a loop over integers from 1 to #t is so
> low (even in C) that you should just do that rather than assume that an
> undocumented behavior will work under all conditions.

That reminds me of the "dual" situation that I once found myself in:

Question: How do you iterate just the "non-array part" (i.e. all entries
excluding those with integer keys 1,2,... up to the first 'nil')?
(Assume that the "array part" contains millions of values (already
traversed in order by numeric for loop), and the "non-array part"
contains optional metadata, i.e. 0 or just a few values, that you now
want to inspect.)

Answer:  You don't.  You use two tables, one for the array-like part,
one for the metadata, and place one inside the other at a "well-known"
key (i.e. one that you can get without calling `next`).  The 56 byte
cost of the extra table is negligible.  (If the array part may be
smaller so that the memory matters, put the metadata in an optional
field in the array and check whether it exists or is nil.)


 *  Trying to jump over part of the next()-traversal by swapping the
    current key passed to next from 1 to #t.  Usually works, but can
    break horribly, for the same reasons previously mentioned in this

 *  Making the keys well-known by arithmetic coding tricks, e.g. store
    t[k]=v as t[i+0.25] = k, t[i+0.75] = v or just keep a list of keys
    at t[i+0.5] = k and store t[k] = v normally, for i=1,2,...
    Really cool but useless hack: costs 64 instead of 32 bytes per
    entry (=costs more starting at 2 entries), needs own iterator, ...