고성능 파이썬(3)

효율적인 탐색

정렬 알고리즘, 탐색 알고리즘

파이썬 리스트는 정렬 알고리즘을 내장하며 팀정렬을 사용한다.

팀정렬은 시간복잡도는 최적일때 0(n), 최악일때 0(n log n)

팀정렬은 삽입정렬, 병합 정렬 알고리즘을 조합해서 최선의 알고리즘을 추측하는 휴리스틱을 사용

bisect 모듈을 이용하여 잘 최적화된 이진 탐색 기법 항목을 찾을수 있을 뿐 아니라

새로운 항목을 추가해도 정렬된 상태가 유지된다.

리스트와 튜플

• 리스트는 동적인 배열이다. 수정이 가능하며, 저장 용량을 늘리거나 줄일 수도 있다.
• 튜플은 정적인 배열이다. 일단 생성되면 배열의 크기뿐 아니라 그 안의 데이터도 변경할 수 없다.
• 튜플은 파이썬 런타임에서 캐시하므로 사용할때마다 커널에 메모리를 요청하지 않아도 된다.

append 를 사용하면 리스트 내포(list comprehension)으로 만들때모다 메모리를 2.7 배 더 사용, 시간은 3배 더 사용

 

튜플이 정적이기 때문에 리스트보다 메모리를 덜 잡아먹는다.

튜플은 리소스 캐싱에서의 이득도 있는데, 파이썬은 GC를 통해 더는 사용되지 않는 변수에 할당된 메모리를 반환한다.

하지만 크기가 20 이하인 튜플은 크기별로 최대 2만 개 까지 즉시 회수하지 않고 나중을 위해 저장해둔다.

이는 다시 필요해지면 운영체제에서 메모리를 새로 할당받지 않고 기존에 할당해둔 메모리를 재사용 할수 있다는 뜻이다. 이로인해 운영체제를 통하지 않음을 튜플을 더 빠르게 생성할수 있다.