목록의 성능 (…) .Insert (…)

Question

컴퓨터 건축에 대한 다음 질문에 대해 생각했습니다. 내가 파이썬에서한다고 가정 해 봅시다

from bisect import bisect
index = bisect(x, a)      # O(log n)  (also, shouldn't it be a standard list function?)
x.insert(index, a)        # O(1) + memcpy()

걸리는 것 log n, 또한, 내가 올바르게 이해하면 메모리 사본 조작 x[index:]. 이제 최근에 병목 현상이 보통 프로세서와 메모리 간의 통신에있어서 메모리 사본을 읽었습니다. ~할 수 있었다 RAM에 의해 매우 빠르게 수행됩니다. 그것이 작동하는 방식입니까?

Answer 1

파이썬은 언어입니다. 여러 구현이 있습니다, 그리고 그들은 5월 목록에 대한 다른 구현이 있습니다. 따라서 실제 구현 코드를 보지 않으면 목록이 구현되는 방법과 특정 상황에서 어떻게 행동하는지 확인할 수 없습니다.

내 내기는 목록의 개체에 대한 참조가 연속 메모리에 저장된다는 것입니다 (확실히 링크 된 목록은 아닙니다 ...). 그것이 실제로 그렇다면, 삽입을 사용하십시오 x.insert 삽입 된 요소 뒤에있는 모든 요소가 이동하게됩니다. 이것은 하드웨어에 의해 효율적으로 수행 될 수 있지만 복잡성은 여전히 에).

작은 목록은 bisect 운영은보다 시간이 더 걸릴 수 있습니다 x.insert, 전자는 있지만 O (로그 N) 후자는 에). 그러나 긴 목록의 경우, 나는 x.insert 병목 현상입니다. 이 경우 다른 데이터 구조를 사용하는 것을 고려해야합니다.

Answer 2

사용 블리스트 모듈 더 나은 삽입 성능이있는 목록이 필요한 경우.

Answer 3

Cpython 목록은 인접한 배열입니다. O (log n) bisect 및 o (n) 삽입물 중 어느 것이 성능 프로파일을 지배하는 것이 목록의 크기와 O () 내부의 일정한 요소에 따라 다릅니다. 특히, BISECT에 의해 호출 된 비교 함수는 목록의 객체 유형에 따라 비싸다.

잠재적으로 큰 돌연변이 가능한 분류 시퀀스를 유지 해야하는 경우 Pythons List 유형의 선형 배열은 선택이 아닙니다. 요구 사항 힙에 따라 나무 또는 건너 뛰기 목록이 적절할 수 있습니다.