Lua: Kopieren einer Tabelle effizient (tiefe Kopie)

Question

Ich versuche, eine Kopie einer Lua-Tabelle effizient zu machen. Ich habe die folgende Funktion copyTable() geschrieben, die gut funktioniert (siehe unten). Aber ich stellte mir vor, dass ich etwas Effizienteres haben könnte, indem ich den "Übergabewert" -Mechanismus der Funktionen nutze. Ich habe ein paar Tests, diesen Mechanismus zu erforschen:

function nop(x) 
    return x 
end 

function noop(x) 
    x={} 
    return x 
end 

function nooop(x) 
    x[#x+1]=4 
    return x 
end 

function copyTable(datatable) 
    local tblRes={} 
    if type(datatable)=="table" then 
    for k,v in pairs(datatable) do tblRes[k]=copyTable(v) end 
    else 
    tblRes=datatable 
    end 
    return tblRes 
end 

tab={1,2,3} 
print(tab)   -->table: 0x1d387e0 tab={1,2,3} 
print(nop(tab))  -->table: 0x1d387e0 tab={1,2,3} 
print(noop(tab))  -->table: 0x1e76f90 tab={1,2,3} 
print(nooop(tab))  -->table: 0x1d387e0 tab={1,2,3,4} 
print(tab)   -->table: 0x1d387e0 tab={1,2,3,4} 
print(copyTable(tab)) -->table: 0x1d388d0 

Wir können sehen, dass der Verweis auf die Tabelle durch die Funktionen unverändert übertragen wird (wenn ich es gerade gelesen oder Dinge hinzufügen), außer in noop(), wo ich versuche, eine radikale Änderung des Bestehenden.

Ich lese Bas Bossink und die Antwort von Michael Anderson in this Q/A. In Bezug auf die Übergabe oder die Tabellen als Argumente betonten sie den Unterschied zwischen "Argumente, die von ref übergeben werden" und "Argumente, die von Werten und Tabellen übergeben werden, sind Referenzen" mit Beispielen, in denen dieser Unterschied auftritt.

Aber was genau bedeutet das? Haben wir eine Kopie der Referenz, aber was für einen Unterschied macht das bei einem Ref-Durchlauf, da die Daten, die auf die Daten zeigen und daher manipuliert werden, immer noch dieselben sind, nicht kopiert? Ist der Mechanismus in noop() spezifisch, wenn wir versuchen, nil auf die Tabelle zu beeinflussen, um die Löschung der Tabelle zu vermeiden oder in welchen Fällen löst sie aus (wir können mit nooop() sehen, dass es nicht immer der Fall ist, wenn Tabelle ist modifiziert)?

Meine Frage: Wie funktioniert der Mechanismus der Weitergabe von Tabellen wirklich? Gibt es eine Möglichkeit, die Daten einer Tabelle effizienter zu kopieren, ohne dass meine CopyTable belastet wird?

Answer 1

Die Regeln der Argumentation in Lua vorbei ist ähnlich zu C: alles ist Pass von Wert, aber Tabellen und Userdaten werden um als Zeiger übergeben. Das Übergeben einer Kopie einer Referenz erscheint in der Verwendung nicht so unterschiedlich, aber es ist völlig anders als die Referenz.

Zum Beispiel haben Sie diesen Teil speziell gebracht.

function noop(x) 
    x={} 
    return x 
end 
print(noop(tab))  -->table: 0x1e76f90 tab={1, 2, 3} 

Sie den Wert für die neue Tabelle zuweisen [1] in variable x (x hält nun einen neuen Zeigerwert). Sie haben die ursprüngliche Tabelle nicht mutiert, die Variable tab enthält immer noch den Zeigerwert für die ursprüngliche Tabelle. Wenn Sie von noop zurückkehren, übergeben Sie den Wert der neuen Tabelle, die leer ist. Variablen enthalten Werte, und ein Zeiger ist ein Wert, keine Referenz.

Edit:

Verpasste Ihre andere Frage. Nein, wenn Sie eine Tabelle tiefkopieren möchten, ist eine Funktion, die der von Ihnen geschriebenen ähnlich ist, der einzige Weg. Tiefe Kopien sind sehr langsam, wenn Tabellen groß werden. Um Performance-Probleme zu vermeiden, könnten Sie einen Mechanismus wie "rewind tables" verwenden, die die an ihnen vorgenommenen Änderungen verfolgen, so dass sie zu späteren Zeitpunkten rückgängig gemacht werden können (sehr nützlich in rekursiven Backtrack-Kontexten). Oder, wenn Sie nur Benutzer davon abhalten müssen, mit den Interna des Tisches zu verschrauben, schreiben Sie eine "freezable" Eigenschaft.

[1] Stellen Sie sich vor die {} Syntax ist eine Funktion, die eine neue Tabelle erstellt und einen Zeiger auf die neue Tabelle zurückgibt.

Answer 2

Wenn Sie sicher sind, dass diese drei Annahmen (A) gelten für "Reiter" (die Tabelle kopiert werden):

1. Es sind keine Tabellenschlüssel

   t1 = {} 
   tab = {} 
   tab[t1] = value 
   

2. Es gibt keine wiederholten Tabellenwerte

   t1 = {} 
   tab = {} 
   tab.a = t1 
   tab.b = t1 
   -- or 
   -- tab.a.b...x = t1 
   

3. Es gibt keine rekursiven Tabellen:

   tab = {} 
   tab.a = tab 
   -- or 
   -- tab.a.b...x = tab 
   

der Code, den Sie dann vorgesehen ist die kleinste und fast so effizient wie möglich.

Wenn A1 nicht gilt (dh Sie haben Tabellenschlüssel), dann müssen Sie Ihren Code ändern:

function copyTable(datatable) 
    local tblRes={} 
    if type(datatable)=="table" then 
    for k,v in pairs(datatable) do 
     tblRes[copyTable(k)] = copyTable(v) 
    end 
    else 
    tblRes=datatable 
    end 
    return tblRes 
end 

Wenn A2 nicht gilt (dh Sie Tabellenwerte wiederholt haben), können Sie dann könnte Ihren Code zu ändern:

function copyTable(datatable, cache) 
    cache = cache or {} 
    local tblRes={} 
    if type(datatable)=="table" then 
    if cache[datatable] then return cache[datatable] 
    for k,v in pairs(datatable) do 
     tblRes[copyTable(k, cache)] = copyTable(v, cache) 
    end 
    cache[datatable] = tblRes 
    else 
    tblRes=datatable 
    end 
    return tblRes 
end 

Dieser Ansatz zahlt sich jedoch nur aus, wenn Sie viele wiederholte große Tabellen haben. Es geht also darum zu bewerten, welche Version für Ihr aktuelles Produktionsszenario schneller ist.

Wenn A3 nicht gilt (d. H. Sie haben rekursive Tabellen), dann wird Ihr Code (und beide Anpassungen oben) in eine unendliche rekursive Schleife eintreten und schließlich einen Stapelüberlauf auslösen.

Der einfachste Weg, das zu behandeln ist eine Zurückverfolgung zu halten und einen Fehler zu werfen, wenn Tabelle Rekursion passiert:

function copyTable(datatable, cache, parents) 
    cache = cache or {} 
    parents = parents or {} 
    local tblRes={} 
    if type(datatable)=="table" then 
    if cache[datatable] then return cache[datatable] 
    assert(not parents[datatable]) 
    parents[datatable] = true 
    for k,v in pairs(datatable) do 
     tblRes[copyTable(k, cache, parents)] 
     = copyTable(v, cache, parents) 
    end 
    parents[datatable] = false 
    cache[datatable] = tblRes 
    else 
    tblRes=datatable 
    end 
    return tblRes 
end 

Meine Lösung für eine deep Funktion, die rekursive Tabellen behandelt, die ursprüngliche Struktur zu bewahren hier zu finden: https://gist.github.com/cpeosphoros/0aa286c6b39c1e452d9aa15d7537ac95