Python的deepcopy（）的运行时复杂度是多少？ [英] What is the runtime complexity of Python's deepcopy()?

问题描述

我正在尝试提高算法的速度，并且在查看了调用了哪些操作之后，我很难准确确定正在减慢速度的因素。我想知道Python的deepcopy（）可能是罪魁祸首，还是我应该进一步研究自己的代码。

I'm trying to improve the speed of an algorithm and, after looking at which operations are being called, I'm having difficulty pinning down exactly what's slowing things up. I'm wondering if Python's deepcopy() could possibly be the culprit or if I should look a little further into my own code.

推荐答案

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

Looking at the code (you can too), it goes through every object in the tree of referenced objects (e.g. dict's keys and values, object member variables, ...) and does two things for them:

1. 在id索引的备忘录字典中查看它是否已被复制


2. 是否复制对象

1. see if it's already been copied, by looking it in id-indexed memo dict
2. copy of the object if not

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

The second one is O(1) for simple objects. For composite objects, the same routine handles them, so over all n objects in the tree, that's O(n). The first part, looking an object up in a dict, is O(1) on average, but O(n) amortized worst case.

因此，平均而言，最多$ deepcopy 是线性的。 备忘录中使用的键是 id（）值，即存储位置，因此它们不会随机分布在键上空格（上面的平均部分），并且可能表现得更糟，直到 O（n ^ 2）最坏的情况。我确实观察到了实际使用中的一些性能下降，但是在大多数情况下，它表现为线性的。

So at best, on average, deepcopy is linear. The keys used in memo are id() values, i.e. memory locations, so they are not randomly distributed over the key space (the "average" part above) and it may behave worse, up to the O(n^2) worst case. I did observe some performance degradations in real use, but for the most part, it behaved as linear.

这是复杂性部分，但是常量很大，并且 deepcopy 并不便宜，并且很可能会引起您的问题。唯一确定的方法是使用探查器-执行此操作。 FWIW，我目前正在重写非常慢的代码，其执行时间的98％花费在 deepcopy 中。

That's the complexity part, but the constant is large and deepcopy is anything but cheap and could very well be causing your problems. The only sure way to know is to use a profiler -- do it. FWIW, I'm currently rewriting terribly slow code that spends 98% of its execution time in deepcopy.

这篇关于Python的deepcopy（）的运行时复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！