这个问题类似于之前发布的问题,How can I deep-compare 2 Lua tables, which may or may not have tables as keys?
事实是,那里的解决方案非常适合简单的深度比较。但是,它不能正确处理循环引用。更具体地说,以下内容:
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
local t1 = {}
t1[t1]=t1
t1.x = {[t1] = {1, 2, 3}}
local t2 = {}
local t3 = {}
t2[t3]=t2
t3[t2]=t3
t2.x = {[t3] = {1, 2, 3}}
t3.x = {[t2] = {1, 2, 3}}
print(table_eq(t1, t2))
--[[>
lua: deeptest.lua:15: stack overflow
stack traceback:
deeptest.lua:15: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
...
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:26: in function <deeptest.lua:3>
(...tail calls...)
deeptest.lua:62: in main chunk
[C]: in ?
--]]
产生堆栈溢出。如果不是堆栈溢出,它可能会产生误报(不是我可以测试的)。
我该如何处理这种情况? (它甚至可以被处理吗?当我想到它时,这听起来像是计算机科学中 Unresolved 问题......但我对此了解不多)
当我说“结构平等”时,我指的是下表:
local t = {}
t[{}] = 1
t["1"] = {}
在结构上与下表不同:
local t = {}
local t2 = {}
t[t2] = 1
t["1"] = t2
而在“内容平等”中,它们是平等的。
测试用例:
local t1 = {}
t1[t1]=t1
t1.x = {[t1] = {1, 2, 3}}
local t2 = {}
local t3 = {}
t2[t3]=t2
t3[t2]=t3
t2.x = {[t3] = {1, 2, 3}}
t3.x = {[t2] = {1, 2, 3}}
assert(table_eq(t1, t2) == false)
assert(table_eq(t2, t3) == true)
local t4 = {}
t4[{}] = 1
t4["1"] = {}
local t5 = {}
local t6 = {}
t5[t6] = 1
t5["1"] = t6
assert(table_eq(t4, t5) == false)
最佳答案
在此示例中,堆栈溢出很容易通过更改以下内容来修复:
-- 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
到:
-- if key is a table, we need to find an equivalent one.
local ok = false
for i, tk in ipairs(t2tablekeys) do
if recurse(k1, tk) and recurse(v1, t2[tk]) then
前 2 个测试用例返回 true,但第 3 个测试用例失败,因为将表作为键进行内容与内容的比较。如果要测试键是否与实际表相同,则需要将其更改为:
-- if key is a table, we need to find an equivalent one.
local ok = false
for i, tk in ipairs(t2tablekeys) do
if k1 == tk and recurse(v1, t2[tk]) then
但是请记住,第二个测试用例会失败,因为您希望将表格作为键来比较内容与内容而不是实际表格。
您的测试用例在您认为“相等”的方面相互矛盾,因此没有真正的答案。
附言
此函数忽略元数据,这也可以与 __eq 元方法进行比较。所以这仍然不是一个完整的比较。
关于algorithm - 我如何在结构上深入比较可能包含循环引用的 2 个 lua 表,其中表的键本身可能是表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39211316/