如何深度比较2个Lua表，可能有也可能没有表作为键？ [英] How can I deep-compare 2 Lua tables, which may or may not have tables as keys?

问题描述

（也发布在Lua邮件列表上）

(Also posted on the Lua mailing list)

所以我一直在写深层算法，我想测试他们是否工作方式我要他们。虽然我可以访问original-> copy map，但我想要一个通用的deep-compare算法，它必须能够比较表键（表为键？）。

So I've been writing deep-copy algorithms, and I wanna test them to see if they work the way I want them to. While I do have access to the original->copy map, I want a general-purpose deep-compare algorithm that must be able to compare table keys (tables as keys?).

我的深度复制演算法可在这里使用： https://gist.github.com/ SoniEx2 / fc5d3614614e4e3fe131 （它不是很有组织，但有3个，一个使用递归调用，另一个使用todo表，其他模拟一个调用堆栈（一个非常丑陋但5.1兼容的方式） ）

My deep-copy algorithm(s) are avaliable here: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (it's not very organized, but there are 3 of them, one uses recursive calls, the other uses a todo table, and the other simulates a call stack (in a very ugly but 5.1-compatible way))

递归版本：

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 （复制

Edit: I found things like this which don't really handle tables as keys: http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3 (Copy of snippet below)

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

b $ b

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

Serializing is also not an option, as order of serialization is "random".

推荐答案

，这取决于你的等价定义。
如果你想这是真的：

As others said, that depends a lot on your definition of equivalence. If you want this to be true:

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

如果你这样做，那么每次t1中的键都是一个表，你必须
在t2中检查其与每个表键的等价性，并通过
one尝试它们。这是一种方法（为了可读性，省略了metatable）。

If you do, then each time the key in t1 is a table, you'll have to check its equivalence with every table key in t2 and try them one by one. This is a way to do it (metatable stuff left out for readability).

function table_eq(table1, table2)
   local avoid_loops = {}
   local function recurse(t1, t2)
      -- compare value types
      if type(t1) ~= type(t2) then return false end
      -- Base case: compare simple values
      if type(t1) ~= "table" then return t1 == t2 end
      -- Now, on to tables.
      -- First, let's avoid looping forever.
      if avoid_loops[t1] then return avoid_loops[t1] == t2 end
      avoid_loops[t1] = t2
      -- Copy keys from 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
      -- Let's iterate keys from t1
      for k1, v1 in pairs(t1) do
         local v2 = t2[k1]
         if type(k1) == "table" then
            -- if key is a table, we need to find an equivalent one.
            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 has a key which t2 doesn't have, fail.
            if v2 == nil then return false end
            t2keys[k1] = nil
            if not recurse(v1, v2) then return false end
         end
      end
      -- if t2 has a key which t1 doesn't have, fail.
      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}}) )

这篇关于如何深度比较2个Lua表，可能有也可能没有表作为键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！