Python3 계산/메모리 표준 유형/데이터 구조 (list, dict, tuple 등)의 복잡성

Question

Python3 기본 데이터 구조 (list, dict, tuple ... 등)의 계산 복잡도는 얼마입니까?

(메모리의 복잡성 문제도 흥미 롭다.)

내가 찾은 무엇

: http://wiki.python.org/moin/TimeComplexity - 나는 그것이, 그것은 파이썬 2 관하여 두려워하지 않는 무엇입니까?

Answer 1

계산상의 복잡성은 의 해결 방법과 관련이 있습니다. 파이썬 3이 더 빠르거나 없다면, 원칙적으로 다른 알고리즘을 사용하여 문제가 해결되지 않는다면 복잡성은 동일 할 것입니다.

때때로 같은 이름을 가진 추상 데이터 구조가 다를 수 있습니다 (예 : Python 2 문자열 대 Python 3 문자열 또는 Python 2의 int, Python 3의 일반화 된 int).

필자는 그것을 검사하지 않았지만, 제 생각에 파이썬 2와 파이썬 3은이 점에서 다르지 않습니다.

Answer 2

위키 항목은 Python 2와 3 모두 CPython에 적용됩니다. 이러한 클래스는 변경되지 않았습니다. 다른 구현은 다를 수 있지만 사람들이 CPython에서 xpython으로 코드를 이식하기를 원한다면 유사해야합니다. 예를 들어 목록 유형에 대한 링크 된 목록을 사용하는 Python은 상당히 다른 프로그래밍 자극 및 코드 재 배열을 필요로합니다.

3.3에서는 dict 클래스가 변경되어 한 클래스의 여러 인스턴스에 공통된 일부 정보가 중복되지 않고 공유됩니다. 이것은 주로 100s 또는 1000s의 인스턴스를 가진 사람들에게 영향을 주며, 공간 복잡성 클래스를 변경하지 않는 상수 요소 인 dict 공간의 약 1/3을 절약 할 것입니다.

더 중요한 것은 (유니 코드) str 클래스가 필요한만큼 많은 바이트/문자 만 사용하도록 완전히 다시 작성된 것입니다. 결과는 일반적으로 공간과 시간이 줄어들지 만, 주 효과는 O (xxx) 표기법에 의해 무시되는 승수에 있어야합니다.