Lua中如何高效比较两个表之间的细微差异？

本文共计631个文字，预计阅读时间需要3分钟。

在Lua中，我创建了两个表：`a` 有18个元素，`b` 有8个元素。我需要返回 `a` 和 `b` 中的公共元素，即 {1, 2, 4, 6}。这类似于Ruby中的命令 `a - b`（如果 `a` 和 `b` 是数组）。

我在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个.