优化 – Lua中两个表之间的差异

我在lua中有两个表(在生产中,a有18个元素,b有8个)：

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

我需要返回’a’省略’b’中的任何公共元素 – {1,2,4,6},类似于ruby命令a-b(如果a和b是数组).

我能想出的最好的lua逻辑是：

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

我需要非常快速地循环这些表格比较(在生产中每秒最少10K次).有更清洁的方法吗？

======

这是redis服务器端脚本的一部分,我必须保护我的Redis CPU.在一个干净的Lua流程之外,我有两个其他选择：

1.创建两个redis临时密钥然后运行烧结以获得42的大(O)

> 18 sadd(a)
> 8 sadd(b)
> 16烧结(a,b)

2.将a和b返回ruby进行数组比较并发回结果.

>后面的网络成本和每秒几千个连接中的第四个将耗尽资源.

你可以这样做(未经测试)：

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

如果你可以修改一个,那就更短了：

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

如果您的表已排序,您还可以将两个表并行扫描,如下面的伪代码：

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

这不使用任何额外的表.即使您想要新表而不是就地差异,也只需要一个新表.我想知道它将如何与哈希表方法(删除)进行比较.

请注意,循环次数无关紧要,如果a和b很小,那么这些与你的alg之间没有重大区别. a和b中至少需要100个项目,甚至可能需要1000个.