Re: table.maxn...

[Coda Highland <chighland@...>]

On Sun, May 31, 2015 at 3:01 PM, Tim Hill <drtimhill@gmail.com> wrote:
> At present, the Lua table API has a “garbage-in, garbage-out” philosophy for
> sequences. But the language provides no easy way to validate sequences, and
> I think that’s a hole. Yes, I can write a reasonably efficient one in C (at
> cost O(n)), but it can’t be as efficient as one baked-into the table
> library, which can leverage it’s internal knowledge much better than code
> that must use the C API.
>
> —Tim

I don't think there's anything that the Lua internals know that could
make this operation any more efficient. To be completely accurate, a
complete O(n) table scan is necessary, as it's really not that hard to
end up with numeric keys in the hash part of a table yet still be a
proper sequence.

That said, a little bit of numeric trickery can improve over your
earlier predicate (it also fixes a slight logical error you had):

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

This uses O(1) space and O(n) time, compared to the O(n) space and
potentially O(n^2) time your function needed (but probably O(n log n)
assuming that Lua grows the array intelligently and uses a smart
sorting algorithm). It works because the counter is unsigned, and for
a proper sequence you will always add and subtract every natural
number between 1 and #t exactly once, while a table with gaps will
result in a positive number.

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

/s/ Adam