Jak mogę głębiej porównać 2 tabele Lua, które mogą lub nie mają tabel jako kluczy?

Question

(Zamieszczone również na liście mailingowej Lua)

Tak więc pisałem algorytmy głębokiego kopiowania i chcę przetestować je, aby sprawdzić, czy działają tak, jak chcę. Chociaż mam dostęp do oryginalnej-> kopii mapy, potrzebuję algorytmu do głębokiego porównania ogólnego zastosowania, który musi być w stanie porównać klucze tabeli (tabele jako klucze?).

Moje algorytmy (kopie) do kopiowania są dostępne tutaj: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (jest niezbyt uporządkowany, ale są 3 z nich, jeden używa wywołań rekursywnych, drugi używa tabeli wywołań, a drugi symuluje stos wywołań (w bardzo brzydki, ale 5,1-kompatybilnym sposób))

wersji rekurencyjne:

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 

Edit: Znalazłem takie rzeczy, które tak naprawdę nie obsługiwać tabele kluczy: http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3 (kopia fragmentu poniżej)

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 

Serializacja również nie jest opcją, ponieważ kolejność serializacji jest "losowa".

Answer 1

Jak powiedzieli inni, zależy to bardzo od definicji równoważności. Jeśli chcesz to prawda:

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

Jeśli tak, to za każdym razem kluczem w T1 jest stół, będziesz musiał sprawdzić jego równoważność z każdym kluczem w tabeli t2 i spróbuj je jeden przez jeden. Jest to sposób na zrobienie tego (spasowane rzeczy pozostawione dla czytelności).

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

Answer 2

Zamiast bezpośredniego porównania możesz spróbować serializować każdą z tabel i porównywać serializowane wyniki. Istnieje kilka serializatorów, które obsługują tabelę jako klucze i mogą serializować struktury głębokie i rekursywne. Na przykład, można spróbować Serpent (dostępny jako moduł autonomiczny, a także zawarte w 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) 

ta zwraca true dla mnie (zarówno Lua Lua 5.1 i 5.2). Jednym z zastrzeżeń jest to, że wynik serializacji zależy od kolejności, w której klucze są serializowane. Tabele jak klucz domyślnie są klasyfikowane na podstawie ich wartości tostring, co oznacza, że ​​kolejność zależy od ich adresem alokacji i to nie trudno wymyślić przykład, że zawodzi pod 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) --<-- `false` under Lua 5.2 

Jednym ze sposobów ochrona przed tym polega na konsekwentnym przedstawianiu tabel przy porównywaniu kluczy; na przykład, zamiast domyślnego tostring, możesz chcieć serializować tabele i ich wartości i sortować klucze na podstawie tego (wąż zezwala na custom handler for sortkeys), co sprawi, że sortowanie będzie bardziej niezawodne, a wyniki serializowane będą bardziej stabilne.