Wie kann ich 2 Lua-Tabellen, die Tabellen als Schlüssel haben können oder nicht?

Question

Also habe ich Deep-Copy-Algorithmen geschrieben, und ich möchte sie testen, um zu sehen, ob sie so funktionieren, wie ich es möchte. Während ich Zugriff auf die Original-> Kopie Karte habe, möchte ich einen Allzweck-Tiefvergleichsalgorithmus, der in der Lage sein muss, Tabellenschlüssel zu vergleichen (Tabellen als Schlüssel?).

Meine Deep-Copy-Algorithmus (en) sind hier verfügbar: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (es ist nicht sehr organisiert, aber es gibt 3 von ihnen, verwendet man rekursive Aufrufe, der andere verwendet eine Todo-Tabelle, und der andere simuliert einen Call-Stack (in einem sehr hässlich, aber 5.1-kompatible Art und Weise))

rekursive Version:

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 

bearbeiten: ich fand Dinge wie diese, die wirklich keine Tabellen als Schlüssel handhaben: http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3 (Kopie des snippet)

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 

Serialisierung ist auch keine Option, da die Reihenfolge der Serialisierung "zufällig" ist.

Answer 1

Wie andere sagten, hängt das sehr von Ihrer Definition der Äquivalenz ab. Wenn Sie wollen, dass diese um wahr zu sein:

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

Wenn Sie das tun, dann wird jedes Mal, wenn der Schlüssel in t1 eine Tabelle, die Sie überprüfen ihre Gleichwertigkeit mit jedem Tabellenschlüssel in t2 sie eine haben werde und versuchen von eins. Dies ist ein Weg, dies zu tun (metatables Zeug für die Lesbarkeit weggelassen).

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

Anstelle des direkten Vergleichs können Sie versuchen, jede der Tabellen zu serialisieren und die serialisierten Ergebnisse zu vergleichen. Es gibt mehrere Serialisierer, die die Tabelle als Schlüssel behandeln und tiefe und rekursive Strukturen serialisieren können. Zum Beispiel können Sie Serpent (als Standalone-Modul und auch in Mobdebug enthalten) versuchen:

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) 

Das gibt true für mich (beide Lua 5.1 und Lua 5.2). Eine der Vorbehalte ist, dass das Serialisierungsergebnis von der Reihenfolge abhängt, in der Schlüssel serialisiert werden. Die Tabellen als Schlüssel standardmäßig auf ihren tostring Wert sortierten basiert, was bedeutet, dass die Reihenfolge auf ihrer Zuteilung Adresse abhängt und es ist nicht schwer, mit einem Beispiel zu entwickeln, die unter Lua versagt 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 

Eine Möglichkeit, davor schützen, Tabellen im Schlüsselvergleich beständig darzustellen; anstelle des Standardwerts tostring möchten Sie möglicherweise Tabellen und ihre Werte serialisieren und die darauf basierenden Schlüssel sortieren (Schlange erlaubt custom handler for sortkeys), was die Sortierung robuster und die serialisierten Ergebnisse stabiler machen würde.