2

我通过将集合的值放在表键中并1作为表值来使用 Lua 表作为集合，例如

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

要测试两组是否相等，我需要确保它们具有完全相同的键。有什么有效的方法来做到这一点？

4

2 回答 2

4

既然你问效率，我将提供一个替代实现。根据您预期的输入表，您可能希望避免第二个循环的查找。如果期望表相同，则效率更高，如果存在差异，则效率较低。

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 的 Parser 决定，因此由源代码令牌的数量决定。对于 Lua，这意味着 Phrogz 的版本很可能是更快的选择。对于 LuaJIT，情况发生了巨大变化，因为解析器不再是问题。对于几乎所有情况，我展示的第一个版本是一个改进，当表非常大时，第二个版本可能是最好的。我建议每个人都运行自己的基准测试并检查哪个版本在他们的环境中效果最好。

于 2013-02-15T06:27:02.170 回答
3

循环遍历两个表并确保键在另一个中具有值。一旦发现不匹配就失败，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-15T06:12:50.357 回答