파이썬의 deepcopy()의 런타임 복잡도는 얼마입니까?

Question

나는 알고리즘의 속도를 향상 시키려고 노력하고 있는데, 어떤 연산이 호출되는지보고 난 후에는 속도를 늦추는 것이 어려워지고있다. Python의 deepcopy()가 범인이 될 수 있는지, 아니면 내 코드를 좀 더 자세히 살펴 봐야하는지 궁금합니다.

Answer 1

(예를 들어, 딕셔너리의 키와 값 객체의 멤버 변수, ...) 그들과 않는 두 가지 :

이미있는 경우 개체의 ID를 인덱스 memo DICT

사본을보고, 복사 않다면

1. 하지

두 번째는 단순한 객체에 대한 O (1)입니다 참조하십시오. 복합 객체의 경우 동일한 루틴에서 처리하므로 모든 n 트리의 객체는 O (n)입니다. dict에서 객체를 찾는 첫 번째 부분은 O(1) on average, but O(n) amortized worst case입니다.

기껏해야 평균적으로 deepcopy은 선형입니다. memo에 사용 된 키는 메모리 위치와 같은 id() 값입니다. 따라서 키 공간 (위의 "평균"부분)에 무작위로 분포하지 않으며 최악의 경우 최대 까지 동작합니다. . 실제 사용에서 일부 성능 저하를 관찰했지만, 대부분 선형으로 동작했습니다.

이것은 복잡성 부분이지만 상수는 크고 deepcopy is anything but cheap이며 큰 문제가 될 수 있습니다. 유일한 확실한 방법은 프로파일 러를 사용하는 것입니다. FWIW, 나는 현재 실행 시간의 98 %를 deepcopy에 보내는 아주 느린 코드를 다시 작성하고 있습니다.

Answer 2

deepcopy()의 복잡도는 복사되는 개체의 크기 (요소 수/자식 수)에 따라 다릅니다.

알고리즘의 입력이 복사되는 객체의 크기에 영향을주지 않으면 각 호출의 실행 시간이 상대적으로 고정되어 있으므로 복잡성을 결정할 때 deeopcopy()의 호출을 O(1)으로 간주해야합니다.

(알고리즘의 입력이 복사되는 물체의 크기에 영향이있는 경우, 당신은. 그런 다음 알고리즘의 복잡성을 평가하는 방법을 자세히 설명해야합니다.)

Answer 3

을 무엇 deepcopy을 사용하고 계십니까? 이름에서 알 수 있듯이 deepcopy은 개체와 모든 하위 개체를 반복적으로 복사하므로 복사중인 개체의 크기에 비례하여 시간이 걸릴 것입니다. (순환 참조를 처리하기 위해 약간의 오버 헤드가 있음)

모든 것을 복사하려고한다면 실제로 속도를 높이는 방법이 없습니다. 모든 것을 복사해야합니다.

한 가지 질문 만하면 모든 것을 복사해야합니까, 아니면 구조의 일부만 복사 할 수 있습니까? (당신도 할 수 있습니다),이 참조 된 개체의 트리의 모든 개체를 통과 코드를 보면