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

Question

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

Answer 1

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

1. memo通过在 id 索引字典中查找来查看它是否已被复制
2. 对象的副本（如果没有）

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

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

这是复杂性部分，但常数很大，而且成本deepcopy不低，很可能会导致您的问题。唯一确定的方法是使用探查器——去做吧。FWIW，我目前正在重写非常慢的代码，其 98% 的执行时间都花在deepcopy.