对于相同大小的列表，为什么深复制比浅复制慢得多？

Question

我一直在开发一个性能关键的应用程序，该应用程序需要经常需要制作二维整数列表的副本并修改副本（我正在实现极小极大算法）。

\n\n

我注意到在具有相同数量元素的列表上，副本和深度复制之间的性能存在巨大差异，我想了解我的想法是否正确。

\n\n

要重现我的问题，请运行以下代码：

\n\n

import numpy as np\n\nnp.random.seed(0)\nlst1 = np.random.randint(100, size=1000 * 1000).tolist()\nlst2 = np.random.randint(100, size=(1000, 1000)).tolist()\n

\n\n

现在，对下面的语句进行计时，您应该会看到与我类似的计时。

\n\n

%timeit copy.copy(lst1)\n%timeit lst1.copy()\n%timeit copy.deepcopy(lst2)\n\n5 ms \xc2\xb1 49.7 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n5.47 ms \xc2\xb1 551 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n1.61 s \xc2\xb1 112 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n

\n\n

和lst1都有lst2一百万个元素，但可靠地复制前者比具有相同数量元素的嵌套列表快 200 倍。我认为这与以下事实有关：制作嵌套列表的深层副本可能需要一些缓慢的递归实现，所以我尝试了

\n\n

%timeit copy.deepcopy(lst1)\n1.43 s \xc2\xb1 90.2 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each) \n

\n\n

而且时间仍然显示出大幅放缓。我已经检查了文档 ，但没有提供太多解释。然而，从时间安排来看，我怀疑它deepcopy也在复制每个int，创建新的整数。但这似乎是一件浪费的事情。

\n\n

我的想法正确吗？深拷贝在这里做什么list.copy而浅拷贝不做什么？

\n\n

我已经看到deepcopy() 非常慢，但似乎问题是要求替代方案而不是解释（我不清楚）。

\n

Answer 1

deepcopy不复制整数。无论如何它都不可能做到这一点。

\n\n

deepcopy速度很慢，因为它需要处理深层复制的全部复杂性，即使事实证明这是不必要的。这包括将它找到的每个对象分派到适当的复印机，即使复印机基本上只是lambda x: x。这包括维护备忘录并跟踪复制的每个对象，以处理对相同对象的重复引用，即使没有。这包括对列表和字典等数据结构的特殊复制处理，因此当尝试使用递归引用复制数据结构时，它不会进入无限递归。

\n\n

所有这些都必须完成，无论是否有回报。所有这一切都很昂贵。

\n\n

而且，deepcopy是纯Python。那没有帮助。deepcopy与pickle.loads(pickle.dumps(whatever))执行非常相似的工作的相比，pickle由于 C 实现而轻松获胜。（在 Python 2 上，替换pickle为cPickle.）pickle仍然很难输给利用已知输入结构的实现，不过：

\n\n

In [15]: x = [[0]*1000 for i in range(1000)]\n\nIn [16]: %timeit copy.deepcopy(x)\n1.05 s \xc2\xb1 5.14 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n\nIn [17]: %timeit pickle.loads(pickle.dumps(x))\n78 ms \xc2\xb1 4.03 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n\nIn [18]: %timeit [l[:] for l in x]\n4.56 ms \xc2\xb1 108 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n

\n