Re: table.maxn...

[Coda Highland <chighland@...>]

On Mon, Jun 1, 2015 at 3:06 AM, Tim Hill <drtimhill@gmail.com> wrote:
> — My reading of the Lua reference is that a sequence can ONLY have integral
> positive keys: “… the set of all positive numeric keys is equal to {1..n}
> for some non-negative integer n” [2.1]. So if the floor() test fails you can
> in fact bail at that point with a false return value. This also takes care
> of the issue of FP errors, since all the math is now done on integers. (That
> was why I didn’t need to check for floor() in my original code and might be
> the “logical error” you referred to.)

Okay, I thought that it had said "the set of all positive integer
keys" there. In that case, drop the floor() check.

> — You don’t really need to do the subtraction of numNumeric in the loop at
> all. Since the sum of the set of integers {1..n} is trivial to compute, you
> can do this once outside the loop and just compare it to the computed sum of
> the all positive integral keys found.

I'm minimizing the risk of overflow. As I commented, my current scheme
requires a computationally-intractable number of elements to break.
Using n(n+1)/2, you break at 134217728 elements -- 134M is large, but
certainly plausible.

> — I agree that any internal Lua implementation would still be O(n), but that
> doesn't mean it cant be faster; not all O(n) code is equal. For example, the
> “array" part of the table can simply be scanned for “nil” values (fast and
> cheap when done internally); no other checks are needed. The code would do
> something like this:

I didn't say it wouldn't be faster. I said it wouldn't be more
efficient. It would be an approximately constant factor of speedup.
(On the other hand, it WOULD make a significant difference in LuaJIT,
as LuaJIT can't currently compile pairs() or next().)

But given the narrowness of the use case, I think this is something
suited for a power patch rather than direct inclusion in the core.

/s/ Adam