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

Question

我一直在开发一个性能关键的应用程序，它经常需要复制一个2D整数列表并修改副本(我正在实现minimax算法)。

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

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

import numpy as np

np.random.seed(0)
lst1 = np.random.randint(100, size=1000 * 1000).tolist()
lst2 = np.random.randint(100, size=(1000, 1000)).tolist()

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

%timeit copy.copy(lst1)
%timeit lst1.copy()
%timeit copy.deepcopy(lst2)

5 ms ± 49.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
5.47 ms ± 551 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1.61 s ± 112 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

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

%timeit copy.deepcopy(lst1)
1.43 s ± 90.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

而且，时差仍然显示出一个巨大的放缓。我检查了文档，但没有给出多少解释。但是，从时间上看，我怀疑deepcopy也在复制每个int，创建新的整数。但这似乎是一件浪费的事情。

我在这里的想法对吗？list.copy和浅拷贝在这里做什么？

我见过深度复制()非常慢，但这个问题似乎是要求另一种选择，而不是解释(对我来说还不清楚)。

Answer 1

deepcopy没有复制ints。反正它也不可能这么做。

deepcopy很慢，因为它需要处理深拷贝的全部复杂性，即使这是不必要的。这包括为它找到的每一个对象分派到适当的复印机，即使复印机是lambda x: x的。这包括维护备忘录，记录复制的每个对象，以处理对相同对象的重复引用，即使没有对象。这包括对数据结构(如列表和小块 )的特殊复制处理，因此当尝试使用递归引用复制数据结构时，它不会进入无限递归。

所有这些都必须做，无论它是否有回报。所有这些都很贵。

而且，deepcopy是纯Python。这没什么用。与执行类似工作的deepcopy和pickle.loads(pickle.dumps(whatever))相比，由于C实现，pickle轻松获胜。(在Python2上，将pickle替换为cPickle.)但是，pickle仍然很难利用输入的已知结构来实现：

In [15]: x = [[0]*1000 for i in range(1000)]

In [16]: %timeit copy.deepcopy(x)
1.05 s ± 5.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [17]: %timeit pickle.loads(pickle.dumps(x))
78 ms ± 4.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [18]: %timeit [l[:] for l in x]
4.56 ms ± 108 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 2

在编程中，深度复制相当于某物的物理副本。它是原始对象的实际副本。在大多数编程工具中，您可以在不影响原始对象的情况下使用它，修改它。但是，另一方面，浅层副本是对原始对象的引用。如果您更改它，它也将影响原始对象。简单地说，由于深拷贝是原始对象的实际拷贝，那么仅仅指向原始对象的浅拷贝就更重了。

浅版:你可以有一张你的新家具的图片，并了解它的真实外观。你可以很容易地随身携带这幅画。

深版:你可以去家具店，看看真正的家具。你可能不容易携带，你可能需要一些帮助才能把它带回家。

Answer 3

https://docs.python.org/2/library/copy.html

浅复制和深度复制之间的区别仅适用于复合对象(包含其他对象的对象，如列表或类实例)：

1. 浅拷贝构造一个新的复合对象，然后(尽可能)将对原始对象的引用插入其中。
2. 深拷贝构造一个新的复合对象，然后递归地将原始对象中的对象的副本插入其中。

因此，实际上，浅拷贝将创建一个新的列表，并通过引用原始列表中的每个元素来填充它。因为原始列表中的每个元素本身都是一个列表，所以只存储对此的引用比创建一个新副本要快得多。Deepcopy在复制每个元素方面做了一些聪明的事情，以避免错误。但从本质上说，你不需要理解为什么一份浅版比一份深度拷贝更快.