Re: table.maxn...

On May 31, 2015, at 3:22 PM, Coda Highland <chighland@gmail.com> wrote:

function isSequence(t)
counter = 0
numNumeric = 0
for k, _ in pairs(t) do
   if (type(k) == "number") and (k > 0) and (k == math.floor(k)) then
     numNumeric = numNumeric + 1
     counter = counter + k - numNumeric
   end
end
return counter == 0
end

(I don't THINK FP precision loss can cause this function to have a
false positive. I've mentally been trying to come up with pathological
failure cases and while the value of counter at the end isn't strictly
what it should be in theory, it's still nonzero. The only exception
would be a sequence with 2^53 keys in it, and that would be impossible
to actually operate on anyway.)

I like this approach. A couple of comments…

— 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.)

— 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 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:

1. Scan the array part of the table (1 to some arbitrary N). If any entry is nil, return false now; it’s not a sequence.

2(a). Scan the hash part for numeric keys where (k > 0). If a (k > 0) key is non-integral, return false now; it’s not a sequence.

2(b). When scanning the hash part, count the numeric keys (M), and compute their (integer) sum S.

3. It’s a sequence if S == sum(N+1..N+M)

Essentially I’m assuming that for larger tables/sequences, the bulk of the (numeric) keys would be in the array part, and that this scanning process would be significantly faster than anything you could do with the Lua C API.

—Tim