Lua: 高效复制表格（深度复制）

Question

Lua: 高效复制表格（深度复制）

luaargumentsparameter-passingdeep-copypass-by-reference-value

6

我试图高效地复制一个lua表。我编写了以下函数copyTable()，它运行良好（见下文）。但是我想象中可以使用函数的“按值传递”机制获得更高效的内容。我进行了一些测试来探索这种机制：

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

我们可以看到，表格的引用通过函数传递时没有改变（当我只是阅读或添加内容），除了在noop()内部尝试对现有内容进行根本修改。

我阅读了Bas Bossink和Michael Anderson在this Q/A中的答案。关于将表格作为参数传递，他们强调了“按引用传递的参数”和“按值传递的参数和表格是引用”的区别，并给出了这种差异出现的例子。

但这具体意味着什么？我们是否拥有引用副本？但与通过引用传递相比，这有什么区别，因为所指向和操作的数据仍然相同，而不是复制？当我们尝试将nil赋给表格时，noop()中的机制是否特定，以避免删除表格，或者在哪些情况下会触发它（我们可以看到，在修改表格时并不总是这种情况）？

我的问题是：传递表格的机制如何工作？是否有一种更有效的方法来复制表格数据而不需要使用copyTable？

- user1771398

1

递归和尾调用。这是你能得到的最高效的方式。 - warspyking

@warspyking：如果我需要组装子表，我能在速度和空间上获得多少优势？当我需要进行尾调用时，该如何“合格”？ - user1771398

1

https://www.lua.org/pil/6.3.html - warspyking

2个回答

1

如果你确定这三个前提条件（A）对于“tab”（被复制的表）是有效的：

没有表键：
```
t1 = {}
tab = {}
tab[t1] = value
```

没有重复的表值：

t1 = {}
tab = {}
tab.a = t1
tab.b = t1
-- 或者
-- tab.a.b...x = t1

没有递归表：

tab = {}
tab.a = tab
-- 或者
-- tab.a.b...x = tab

你提供的代码是最小的，几乎是尽可能高效的。

如果A1不成立（即你有表键），那么你必须更改你的代码为：

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

如果A2不包含（即您有重复的表值），那么您可以更改代码为：

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

这种方法只有在您有大量重复的大型表格时才会得到回报。因此，评估哪个版本对您的实际生产场景更快是很重要的。

如果A3不成立（即您有递归表），那么您的代码（以及上述两个调整）将进入无限递归循环，并最终抛出堆栈溢出。

处理这种情况的最简单方法是保持回溯并在发生表递归时抛出错误：

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

我处理递归表的深度复制函数解决方案，保留原始结构，可以在这里找到：https://gist.github.com/cpeosphoros/0aa286c6b39c1e452d9aa15d7537ac95

- Rodrigo Oliveira Perez

有一个函数“开箱即用”执行深拷贝在各种情况下是很有趣的。您能解释一下函数deepCopy（value，cache，promises，copies）的变量是什么，或者/和给出一个工作示例吗？ - user1771398

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ktb · Accepted Answer

Lua中的参数传递规则和C语言类似：所有的值都是按值传递，但表和用户数据作为指针传递。传递引用的副本在使用上看起来并不那么不同，但与按引用传递完全不同。

例如，你特别提到了这一部分。

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

你将新表[1]的值分配给变量x（x现在持有一个新的指针值）。你没有改变原始表，tab变量仍然持有指向原始表的指针值。当你从noop返回时，你传回了空表的值，这个新表是空的。变量保存值，指针是一个值，不是一个引用。

编辑：

错过了你另一个问题。如果你想要深度复制一个表，类似于你写的函数是唯一的方法。当表变得很大时，深拷贝非常缓慢。为了避免性能问题，你可以使用类似于“重置表”的机制，它们跟踪对它们所做的更改，以便稍后可以撤消（在递归回溯环境中非常有用）。或者，如果你只需要防止用户搞乱表内部，那么写一个“可冻结”的特性即可。

[1] 想象一下{}语法是一个构造新表并返回指向新表的指针的函数。