4
votes

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.
3
Do you have control over how you define the tables a and b? - hjpotter92
to some degree yes. thinking sets? - tjrburgess

3 Answers

6
votes

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

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.

0
votes

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]"
  }
}