15
이 정보에 대한 소스를 찾을 수 없었습니다. 파이썬 소스 코드를 직접 보지 않아도 객체가 어떻게 작동하는지 알 수 없었습니다. 누구든지이 온라인을 어디에서 찾을 수 있는지 알고 있습니까?파이썬에서 내장 시퀀스 유형의 시간과 공간 복잡성은 어디서 찾을 수 있습니까?
A
답변
17
py dot org 위키의 TimeComplexity 페이지를 확인하십시오. 그것은 적어도 시간 복잡성이 간다면 set/dicts/lists/etc를 다루고 있습니다.
2
내가 묻는 것이 궁금하면, Here ... 476 페이지를 참조하십시오.
이것은 파이썬 최적화 기술에 관한 글입니다. 시간 효율성에 대한 빅 오 (Big-O) 표기는 대부분 메모리가 아닙니다.
13
Raymond D. Hettinger는 'Core Python Containers - Under the Hood'라는 Python의 내장 컬렉션에 대해 an excellent talk (slides)을 수행합니다. 내가 본 버전은 주로 set과 dict이지만, list도 다루어졌습니다.
또한 EuroPython의 관련 슬라이드 사진이 a blog입니다. 포인터의 배열로
- 상점 항목 : 여기 는
list에 내 노트를 요약 한 것입니다. 첨자 비용은 O (1) 시간입니다. 추가 비용 O (1) 시간 상각. 삽입 비용은 O (n)입니다. - 과도하게 할당하여 성장할 경우
memcpy을 피하려고합니다. 많은 소규모 목록은 많은 공간을 낭비 할 것이지만 큰 목록은 번식에 약 12.5 % 이상을 낭비하지 않습니다. - 일부 작업은 사전 크기입니다. 주어진 예는
range(n),map(),list(),[None] * n및 슬라이싱이었다. - 축소 할 때 배열은 공간의 50 %를 낭비하는 경우에만
realloc입니다.pop저렴합니다.