  lua-l archive

• Subject: Re: Lua 5.2 Length Operator and tables (bug?)
• From: Roberto Ierusalimschy <roberto@...>
• Date: Wed, 18 Apr 2012 14:00:17 -0300

```> Suppose that we patch a Lua interpreter slightly to add another field
> to the "Table" structure - i.e., to:
>
>   http://www.lua.org/source/5.2/lobject.h.html#Table

This change would increase the size of any empty table by 12%.

> Let's call this new field "npik", for the "number of positive integer
> keys" in the table. It is relatively cheap to keep it up to date - we
> only need to modify the code that implements "T[key] = val".

The change is simple, but not too simple. (It has to consider the
four kinds of changes: nil->nil, nil->non-nil, non-nil->nil, and
non-nil->non-nil.) Moreover, its cost will be at least O(n) on the
size of the table (only it will be amortized).

> Suppose that we add a function "npik" that reads the npik field of a
> table; then we can implement "issequence" as just the translation of
> this to C:
>
>     issequence = function (T)
>         for i=1,npik(T) do
>           if T[i] == nil then return false end
>         end
>         return true
>       end

This is still a O(n) operation. I do not think we need 'npik' to write
an O(n) 'issequence' function:

function issequence (t)
local n = #t    -- assumes 5.1 definition
local i = 0
for k in pairs(t) do
if type(k) == 'number' and k > 0 then   -- positive numeric key?
if k ~= math.floor(k) or k > n then   -- not in set {1..n} ?
return false
end
i = i + 1  -- count it
end
end
return i == n   -- set is complete?
end

-- Roberto

```