2

この質問は、以前に投稿された質問「How can I deep-compare 2 Lua tables, which may or 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 ?
--]]

スタック オーバーフローを生成します。また、スタック オーバーフローがなければ、代わりに誤検知が発生する可能性があります (テストできるわけではありません)。

この場合、どうすればよいですか？（でも扱えるのか？ そう考えると計算機科学の未解決問題のように聞こえるが……よくわからない）

「構造的同等性」とは、次の表を意味します。

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

1 に答える 1

1

この例のスタック オーバーフローは、次のように変更することで簡単に修正できます。

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

ただし、実際のテーブルではなく、コンテンツとコンテンツを比較するキーとしてテーブルを期待しているため、2 番目のテスト ケースは失敗することに注意してください。

あなたのテストケースは、あなたが「等しい」と考えるものについて互いに矛盾しているため、本当の答えはありません。

Ps

この関数はメタデータを無視するため、__eq メタメソッドと比較することもできます。とにかく、それはまだ完全な比較ではありません。

于 2016-09-17T15:08:55.953 に答える