Pythonのdeepcopy（）の実行時の複雑さは何ですか？

Question

私はアルゴリズムの速度を向上させようとしています。どの操作が呼び出されているのかを見て、遅くなっているものを正確に固定するのが難しいです。私はPythonのdeepcopy（）がおそらく犯人になる可能性があるのか​​、それとも私自身のコードを少し詳しく見なければならないのだろうかと思います。

Answer 1

（例えば辞書のキーと値、オブジェクトのメンバ変数、...）彼らのためにとし二つのこと：

1. それは既に第二つO単純なオブジェクト（1）でない

場合、オブジェクトのIDインデックスmemo辞書

コピーでそれを見ることによって、コピーされますかどうかを確認。複合オブジェクトの場合、同じルーチンがそれらを処理します。したがって、nのオブジェクトは、ツリー内のオブジェクトです。O（n）です。最初の部分は、dictでオブジェクトを探して、O(1) on average, but O(n) amortized worst caseです。

最高で平均してdeepcopyは線形です。 memoで使用されるキーはid()の値、すなわちメモリの場所なので、キースペース（上記の「平均」部分）にランダムには分散されず、悪化する可能性があります（最大でO（n^2）） 。私は実際の使用でいくつかの性能低下を観察しましたが、大部分は線形として動作しました。

これは複雑な部分ですが、定数が大きく、deepcopy is anything but cheapという大きな問題が発生する可能性があります。唯一の知るべき唯一の方法は、プロファイラを使用することです。 FWIW、私は現在、実行時間の98％を費やす非常に遅いコードをdeepcopyに書き直しています。

Answer 2

deepcopy()の複雑さは、コピーされているオブジェクトのサイズ（要素数/子）によって異なります。

アルゴリズムの入力がコピーされるオブジェクトのサイズに影響しない場合は、各呼び出しの実行時間が比較的静的なため、複雑さを判断するためにdeeopcopy()への呼び出しをO(1)と考える必要があります。

（自分のアルゴリズムの入力はコピーされているオブジェクト（複数可）の大きさに影響を持っている場合は、その後、アルゴリズムの複雑さを評価できる方法を詳しく説明する必要があります。）

Answer 3

をしている何あなたのためにdeepcopyを使用していますか？名前からわかるように、deepcopyはオブジェクトとすべてのサブオブジェクトを再帰的にコピーするので、コピーしているオブジェクトのサイズに比例した時間がかかります。

すべてをコピーする場合は、すべてをコピーする必要があります。スピードアップする方法はありません。

質問すると、すべてをコピーする必要がありますか、または構造の一部をコピーするだけですか？ （あなたもすることができます）、それが参照されるオブジェクトのツリー内のすべてのオブジェクトを通過するコードを見てみると