如何在 Lua 中深入比较 2 个表，这些表可能有或没有表作为键？

2018-10-3 2:34:17
收藏：0
阅读：115
评论：2

我一直在编写深层复制算法，并想测试它们是否按照我希望的方式工作。虽然我可以访问原始->副本映射，但我想要一个通用的深度比较算法，它必须能够比较表键（表作为键？）。

我的深层复制算法在此处可用：https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131（它不是很有条理，但是有3个版本，一个使用递归调用，另一个使用待办表，另一个使用一个非常丑陋但与5.1兼容的调用堆栈模拟）

递归版本：

local function deep(inp,copies)
  if type(inp) ~= "table" then
    return inp
  end
  local out = {}
  copies = (type(copies) == "table") and copies or {}
  copies[inp] = out -- use normal assignment so we use copies' metatable (if any)
  for key,value in next,inp do -- skip metatables by using next directly
    -- we want a copy of the key and the value
    -- if one is not available on the copies table, we have to make one
    -- we can't do normal assignment here because metatabled copies tables might set metatables

    -- out[copies[key] or deep(key,copies)]=copies[value] or deep(value,copies)
    rawset(out,copies[key] or deep(key,copies),copies[value] or deep(value,copies))
  end
  return out
end

编辑：我发现像这样的东西实际上不能处理表作为键：http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3（下面是片段的副本）

function deepcompare(t1,t2,ignore_mt)
  local ty1 = type(t1)
  local ty2 = type(t2)
  if ty1 ~= ty2 then return false end
  -- non-table types can be directly compared
  if ty1 ~= 'table' and ty2 ~= 'table' then return t1 == t2 end
  -- as well as tables which have the metamethod __eq
  local mt = getmetatable(t1)
  if not ignore_mt and mt and mt.__eq then return t1 == t2 end
  for k1,v1 in pairs(t1) do
    local v2 = t2[k1]
    if v2 == nil or not deepcompare(v1,v2) then return false end
  end
  for k2,v2 in pairs(t2) do
    local v1 = t1[k2]
    if v1 == nil or not deepcompare(v1,v2) then return false end
  end
  return true
end

序列化也不是一个选项，因为序列化的顺序是“随机”的。

点赞
用户1442917
用户1442917

相比直接比较，你可以尝试将每个表进行序列化并比较序列化结果。有几种序列化器能够处理作为键的表并序列化深嵌套结构。例如，你可以尝试 Serpent（作为一个独立的模块和在 Mobdebug 中都可用）：

local dump = pcall(require, 'serpent') and require('serpent').dump
  or pcall(require, 'mobdebug') and require('mobdebug').dump
  or error("can't find serpent or mobdebug")
local a = dump({a = 1, [{}] = {}})
local b = dump({[{}] = {}, a = 1})
print(a==b)

我这里会得到 true（在 Lua 5.1 和 Lua 5.2 上都一样）。其中的一个注意事项是序列化结果依赖于键的序列化顺序。默认情况下，键为表的表是按照它们的 tostring 值进行排序的，这意味着顺序依赖于它们的分配地址，很容易想出在 Lua 5.2 下会失败的例子：

local dump = pcall(require, 'serpent') and require('serpent').dump
  or pcall(require, 'mobdebug') and require('mobdebug').dump
  or error("can't find serpent or mobdebug")
local a = dump({a = 1, [{}] = {1}, [{}] = {2}})
local b = dump({[{}] = {2}, a = 1, [{}] = {1}})
print(a==b) --<-- 在 Lua 5.2 下会得到 `false`

一种避免这种情况的方法是在进行键比较时一致地表示表。例如，你可以序列化表及其值并根据此对键进行排序（serpent 允许为 sortkeys 提供一个自定义处理程序），这样排序就更加健壮，序列化结果也更加稳定。

2014-09-19 17:05:51
用户1793220
用户1793220

如其他人所说, 这很大程度上取决于您对等价性的定义。

如果您想让这个语句成立:

local t1 = {[{}] = {1}, [{}] = {2}}
local t2 = {[{}] = {1}, [{}] = {2}}
assert( table_eq(t1, t2) )

假如每次t1中的键是一个表的时候, 您需要检查它与t2中的每个表键是否相等, 并逐个尝试。以下是一种方法(由于可读性而省略了metatable部分)。

function table_eq(table1, table2)
   local avoid_loops = {}
   local function recurse(t1, t2)
      -- 比较值类型
      if type(t1) ~= type(t2) then return false end
      -- 基本情况: 比较简单的值
      if type(t1) ~= "table" then return t1 == t2 end
      -- 现在我们来到表。
      -- 首先, 让我们避免永远循环。
      if avoid_loops[t1] then return avoid_loops[t1] == t2 end
      avoid_loops[t1] = t2
      -- 从t2复制键
      local t2keys = {}
      local t2tablekeys = {}
      for k, _ in pairs(t2) do
         if type(k) == "table" then table.insert(t2tablekeys, k) end
         t2keys[k] = true
      end
      -- 让我们从t1的键中遍历
      for k1, v1 in pairs(t1) do
         local v2 = t2[k1]
         if type(k1) == "table" then
            -- 如果键是一个表, 我们需要找到一个等价的表。
            local ok = false
            for i, tk in ipairs(t2tablekeys) do
               if table_eq(k1, tk) and recurse(v1, t2[tk]) then
                  table.remove(t2tablekeys, i)
                  t2keys[tk] = nil
                  ok = true
                  break
               end
            end
            if not ok then return false end
         else
            -- t1拥有一个t2没有的键, 失败。
            if v2 == nil then return false end
            t2keys[k1] = nil
            if not recurse(v1, v2) then return false end
         end
      end
      -- 如果t2拥有一个t1没有的键, 失败。
      if next(t2keys) then return false end
      return true
   end
   return recurse(table1, table2)
end

assert( table_eq({}, {}) )
assert( table_eq({1,2,3}, {1,2,3}) )
assert( table_eq({1,2,3, foo = "fighters"}, {["foo"] = "fighters", 1,2,3}) )
assert( table_eq({{{}}}, {{{}}}) )
assert( table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {2}}) )
assert( table_eq({a = 1, [{}] = {}}, {[{}] = {}, a = 1}) )
assert( table_eq({a = 1, [{}] = {1}, [{}] = {2}}, {[{}] = {2}, a = 1, [{}] = {1}}) )

assert( not table_eq({1,2,3,4}, {1,2,3}) )
assert( not table_eq({1,2,3, foo = "fighters"}, {["foo"] = "bar", 1,2,3}) )
assert( not table_eq({{{}}}, {{{{}}}}) )
assert( not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {2}, [{}] = {3}}) )
assert( not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {3}}) )
2014-09-22 14:32:59

作者:

用户3691554

用户3691554
推荐文章