StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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:</p> <ol> <li>see if it's already been copied, by looking it in id-indexed <code>memo</code> dict</li> <li>copy of the object if not</li> </ol> <p>The second one is <em>O(1)</em> for simple objects. For composite objects, the same routine handles them, so over all <em>n</em> objects in the tree, that's <em>O(n)</em>. The first part, looking an object up in a dict, is <a href="http://wiki.python.org/moin/TimeComplexity" rel="nofollow"><em>O(1)</em> on average, but <em>O(n)</em> amortized worst case</a>.</p> <p>So at best, on average, <code>deepcopy</code> is linear. The keys used in <code>memo</code> are <code>id()</code> 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 <em>O(n^2)</em> worst case. I did observe some performance degradations in real use, but for the most part, it behaved as linear.</p> <p>That's the complexity part, but the constant is large and <a href="http://writeonly.wordpress.com/2009/05/07/deepcopy-is-a-pig-for-simple-data/" rel="nofollow"><code>deepcopy</code> is anything but cheap</a> 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 <code>deepcopy</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload