判断两个表是否具有相同的键集。

2013-2-22 23:33:42
收藏：0
阅读：202
评论：2

我将 Lua 表格用作集合，将集合的值放在表格键中，将 1 作为表格值，例如：

function addToSet(s,...)      for _,e in ipairs{...} do s[e]=1   end end
function removeFromSet(s,...) for _,e in ipairs{...} do s[e]=nil end end

local logics = {}
addToSet(logics,true,false,"maybe")

要测试两个集合是否相等，我需要确保它们具有完全相同的键。有没有高效的方法可以做到这一点？

点赞
用户405017
用户405017

循环遍历这两个表格并确保键在另一个表格中具有值。如果找到不匹配的情况，则立即失败；如果遍历完两个表格没有发现不匹配，返回true 。对于大小为M和N的集合来说，其时间复杂度为O(M+N)。

function sameKeys(t1,t2)
  for k,_ in pairs(t1) do if t2[k]==nil then return false end end
  for k,_ in pairs(t2) do if t1[k]==nil then return false end end
  return true
end

在操作中看到：

local a,b,c,d = {},{},{},{}
addToSet(a,1,2,3)
addToSet(b,3,1,2,3,3,1)
addToSet(c,1,2)
addToSet(d,2,1)
print(sameKeys(a,b)) --> true
print(sameKeys(a,c)) --> false
print(sameKeys(d,c)) --> true

注意，测试t[k]==nil比not t[k]更好，以处理（不太可能出现的）情况，即您已经为表格条目设置了一个false的值，并且您希望该键存在于集合中。

2013-02-15 06:12:50
用户2073257
用户2073257

由于您关心效率问题，我会提供一种替代实现。取决于您期望的输入表格，您可能希望避免第二个循环的查找。如果预计表格相同，则效率更高，如果存在差异，则效率较低。

function sameKeys(t1,t2)
  local count=0
  for k,_ in pairs(t1) do
    if t2[k]==nil then return false end
    count = count + 1
  end
  for _ in pairs(t2) do
    count = count - 1
  end
  return count == 0
end

另一个版本避免查找，除非必要。这在另一组用例中可能表现得更快。

function sameKeys(t1,t2)
  local count=0
  for _ in pairs(t1) do count = count + 1 end
  for _ in pairs(t2) do count = count - 1 end
  if count ~= 0 then return false end
  for k,_ in pairs(t1) do if t2[k]==nil then return false end end
  return true
end

编辑：经过更多调研和测试，我得出结论需要区分Lua和LuaJIT。对于Lua，性能特征由Lua的解析器主导，并且由源代码记号的数量决定。对于Lua来说，这意味着Phrogz的版本很可能是更快的替代方案。对于LuaJIT，情况发生了巨大变化，因为解析器不再是问题。对于几乎所有情况，我展示的第一版本都是一种改进，当表格非常大时，第二个版本可能最好。我建议每个人运行自己的基准测试，并检查哪个版本在其环境中最好。

2013-02-15 06:27:02

作者:

用户405017

用户405017
推荐文章