Lua中两个表之间的差异

Question

我在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命令ab(如果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进行数组比较并发回结果.

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

Answer 1

试试这个:

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

Answer 2

你可以这样做（未经测试）：

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

如果你可以修改的a话，它会更短：

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

这不使用任何额外的表。即使您想要新表而不是就地差异，也只需一张新表。我想知道它与哈希表方法相比如何（remove）。

请注意，循环多少次并不重要，如果a和b都很小，那么它们和您的算法之间不会有太大区别。a您将需要 中和 中至少 100 个项目b，甚至可能需要 1000 个。