Python的deepcopy()的运行时复杂度是多少？

Question

我正在尝试提高算法的速度，在查看调用了哪些操作之后，我很难确定究竟是什么导致了速度变慢。我想知道 Python 的 deepcopy() 是否可能是罪魁祸首，或者我是否应该进一步研究我自己的代码。

Answer 1

查看代码（你也可以），它遍历引用对象树中的每个对象（例如字典的键和值，对象成员变量，...）并为它们做两件事：

1. 通过在 id-indexed

   memo

   dict
中查看它是否已经被复制
2. 如果不是对象的副本

第二个是简单对象的O(1)。对于复合对象，相同的例程处理它们，因此在树中的所有 n 对象上，这是 O(n)。第一部分，在字典中查找对象，平均为 O(1)，但 O(n) 摊销的最坏情况。

所以充其量，平均而言，

deepcopy

是线性的。

memo

中使用的键是

id()

值，即内存位置，因此它们不是随机分布在键空间（上面的“平均”部分）并且它可能表现更差，直到 O(n^2 ) 最坏的情况。我确实在实际使用中观察到一些性能下降，但在大多数情况下，它表现为线性。

那是复杂性部分，但常数很大，

deepcopy

绝不便宜，很可能会导致您的问题。唯一确定的方法是使用分析器——去做吧。 FWIW，我目前正在重写非常慢的代码，其 98% 的执行时间都花在

deepcopy

.

Answer 2

你用

deepcopy

做什么？顾名思义，

deepcopy

递归地复制对象和所有子对象，因此需要的时间与您复制的对象的大小成正比。 （处理循环引用需要一些开销）

真的没有办法加快速度，如果你要复制所有东西，你需要复制所有东西。

一个问题要问，你需要复制所有的东西，还是只复制部分结构。

Answer 3

deepcopy()

的复杂性取决于被复制对象的大小（元素/子元素的数量）。

如果您的算法的输入不影响被复制对象的大小，那么为了确定复杂性，您应该将对

deepcopy()

的调用视为

O(1)

，因为每次调用的执行时间都是相对静态的。

（如果你的算法的输入确实对被复制对象的大小有影响，你必须详细说明如何。然后可以评估算法的复杂性。）

Answer 4

如果你看到copy module的源代码，你可以看到函数

deepcopy()

处理实际上取决于提供的输入类型。

例如，如果输入类型是列表，那么处理由

list.copy

function完成。其时间复杂度为

O(n)

。 同样，对于集合，它也是

O(n)

.