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