Lua : 复制表格的高效方法(深拷贝)

我尝试高效地复制一个 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 BossinkMichael Anderson这个 Q/A 中提供的答案。关于将表格作为参数传递的问题,他们强调了“按引用传递的参数”和“按值传递的参数,而表格是引用”之间的区别,并提供了例子以显示该区别的不同之处。

但具体是什么意思呢?我们是复制了引用,但是与通过引用传递有什么不同呢,因为所指向的数据仍然是相同的,而不是复制的?noop() 中的机制是特定的,当我们尝试将 nil 赋予表格时,是特定的以避免删除表格,或者在哪种情况下会触发(我们可以看到使用 nooop() 不总是在修改表格时都会触发)?

我的问题:这个传递表格的机制是如何工作的?是否有更高效的方法来复制表格的数据而不会增加我的复制表的负担?

点赞
用户6614127
用户6614127

Lua 中的参数传递规则与 C 相似:所有的值都是按值传递,但是表和用户数据作为指针传递。传递引用的副本在使用上似乎没有太大的区别,但与引用传递完全不同。

例如,你特别提出了这一部分。

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

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

编辑:

忘记回答你的另一个问题了。不,如果你想深拷贝一个表,类似于你写的函数是唯一的方法。当表变得很大时,深层拷贝非常慢。为了避免性能问题,你可以使用像“回滚表”这样的机制来跟踪对它们所做的更改,以便以后可以撤消(在递归回溯上非常有用)。或者如果你只需要防止用户捣乱表内部,写一个“可冻结”的特征。

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

2017-02-11 17:36:15
用户2945330
用户2945330

如果你确定这三个假设(A)对于“tab”(被复制的表)是有效的:

  1. 没有表键

    t1 = {}
    tab = {}
    tab[t1] = value
    
  2. 没有重复的表值

    t1 = {}
    tab = {}
    tab.a = t1
    tab.b = t1
    -- 或者
    -- tab.a.b...x = t1
    
  3. 没有递归表:

    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

2017-08-24 16:46:06