Differences between two tables in Lua

问题:

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.

回答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.

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