Differences between two tables in Lua

Question

I have two tables in lua (In production, a has 18 elements and b has 8):

local a = {1,2,3,4,5,6}
local b = {3,5,7,8,9}

I need to return 'a' omitting any common elements from 'b' -- {1,2,4,6} similar to the ruby command a-b (if a and b were arrays).

The best lua logic I have been able to come up with is:

local function find(a, tbl)
    for _,a_ in ipairs(tbl) do if a_==a then return true end end
end

function difference(a, b)
   local ret = {}
   for _,a_ in ipairs(a) do
   if not find(a_,b) then table.insert(ret, a_) end
end

return ret
end

local a = {1,2,3,4,5,6}
local b = {3,5,7,8,9}

local temp = {}
temp = difference(a,b)

print(temp[1],temp[2],temp[3],temp[4])

I need to loop through these table comparison pretty quick (min 10K times a second in production). Is there a cleaner way to do this?

======

This is part of a redis server side script and I have to protect my Redis CPU. Outside of a clean Lua process I have two other options:

1.Create two redis temp keys then run sinter for a big(O) of 42

• 18 sadd(a)
• 8 sadd(b)
• 16 sinter(a,b)

2.Return both a and b to ruby do the array comparison and send back the result.

• Network cost of the back and fourth of a few thousand connections a second will be a drain on resources.

Sesquicarbonate

Do you have control over how you define the tables a and b? – Mucronate

to some degree yes. thinking sets? – Sesquicarbonate

Answer 1

You could do this (not tested):

function difference(a, b)
    local ai = {}
    local r = {}
    for k,v in pairs(a) do r[k] = v; ai[v]=true end
    for k,v in pairs(b) do 
        if ai[v]~=nil then   r[k] = nil   end
    end
    return r
end

If you can modify a then it is even shorter:

function remove(a, b)
    local ai = {}
    for k,v in pairs(a) do ai[v]=true end
    for k,v in pairs(b) do 
        if ai[v]~=nil then   a[k] = nil   end
    return r
end

If your tables are sorted you could also do a parallel sweep of the two tables together, something like the following pseudo code:

function diff(a, b)
    Item = front of a
    Diff = front of b
    While Item and Diff
       If Item < Diff then 
           Item is next of a
       Else if Item == Diff then 
           remove Item from a
           Item = next of a
           Diff = next of b
       Else         # else Item > Diff
           Diff = next of b

This doesn't use any extra tables. Even if you want new table instead of in-place diff, only one new table. I wonder how it would compare to the hash table method (remove).

Note that it doesn't matter how many times you loop, if a and b are small then there will be no major difference between these and your alg. You'll need at least 100 items in a and in b, maybe even 1000.

Revulsion

Doing some basic bench testing on my standard MacBook Pro shows this this difference function to run ~5% faster compared to other versions. The remove function runs an additional ~5% faster. – Sesquicarbonate

Answer 2

Try this:

function difference(a, b)
    local aa = {}
    for k,v in pairs(a) do aa[v]=true end
    for k,v in pairs(b) do aa[v]=nil end
    local ret = {}
    local n = 0
    for k,v in pairs(a) do
        if aa[v] then n=n+1 ret[n]=v end
    end
    return ret
end

Rideout

i did a simple benchmark on lua.org/cgi-bin/demo. At 100K loops your code took .22s, mine took .26s and the gap widens with increased number of elements. – Sesquicarbonate

@tjrburgess, searching tables is not the Lua way. Anyway, your algorithm is O(mn) where m and n are the sizes of the tables. Mine is O(m+n) but uses more memory. Not that any of this matter with small tables – Rideout

Answer 3

Maybe something like that:

function get_diff (t1, t2) 
    local diff = {}
    local bool = false
    for i, v in pairs (t1) do
        if t2 and type (v) == "table" then
            local deep_diff = get_diff (t1[i], t2[i]) 
            if deep_diff then
                diff[i] = deep_diff
                bool = true
            end
        elseif t2 then
            if not (t1[i] == t2[i]) then
                diff[i] = t1[i] .. ' -- not [' .. t2[i] .. ']'
                bool = true
            end
        else 
            diff[i] = t1[i]
            bool = true
        end
    end
    
    if bool then
        return diff
    end
end

local t1 = {1, 2, 3, {1, 2, 3}}
local t2 = {1, 2, 3, {1, 2, 4}}
local diff = get_diff (t1, t2) 

Result:

diff = {
  nil,
  nil,
  nil,
  {
    [3] = "3 -- not [4]"
  }
}

Girhiny

Please explain what your code does and how it does it. – Predate

The function searches the different between two tables and returns the string where is the different with the same keys. So, if you have two tables t1 and t2, then it prints the different between values on every table layer. So the diff[4][3] has different between t1[4][3] and t2[4][3], as sting. – Girhiny