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

Question

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

Answer 1

查看代码(您也可以)，它遍历引用对象树中的每个对象(例如字典的键和值、对象成员变量……)并为它们做两件事:

1. 通过在 id-indexed memo dict 中查看它是否已经被复制
2. 如果没有则复制对象

对于简单对象，第二个是O(1)。对于复合对象，相同的例程处理它们，因此在树中的所有 n 个对象上，这是 O(n)。第一部分，在字典中查找对象，是 O(1) on average, but O(n) amortized worst case .

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

那是复杂度的部分，但是常数很大而且 deepcopy is anything but cheap并且很可能会导致您的问题。唯一确定的方法是使用分析器——去做吧。 FWIW，我目前正在重写非常慢的代码，其 98% 的执行时间都花在 deepcopy 中。