고성능 파이썬(4)

CHAPTER 3. 리스트와 튜플

 

3.1. 더 효율적인 탐색

파이썬 리스트는 정렬 알고리즘을 내장하고 있으며 팀(Tim) 정렬을 사용한다. 팀 정렬은 최적의 경우 O(n), 최악의 경우 O(nlogn)의 시간 복잡도를 가진다. 팀 정렬은 다양한 정렬 알고리즘을 활용하여 주어진 데이터에 어떤 알고리즘을 적용하는 것이 최선인지를 추측하는 휴리스틱을 사용한다(더 자세히 말하자면, 삽입 정렬과 병합 정렬 알고리즘을 조합해서 사용한다).

 

리스트를 정렬하고 나면 평균 O(log n)의 복잡도를 가지는 이진 탐색을 사용해서 항목을 찾는다. 이진 탐색은 리스트의 가운데 값과 찾고자 하는 값을 비교한다. 가운데 값이 찾고자 하는 값보다 작다면 찾으려는 값은 리스트의 오른쪽에 있을 것이다. 이런 식으로 값을 찾을 떄까지 리스트를 작게 나누어 탐색한다.

 

def binary_search(needle, haystack):
  imin, imax = 0, len(haystack)
  while True:
    if imin >= imax:
      return -1
    midpoint = (imin + imax) // 2
    if haystack[midpoint] > needle:
      imax = midpoint
    elif haystack[midpoint] < needle:
      imin = midpoint+1
    else:
      return midpoint

이 함수는 잠재적으로 무거울 수도 있는 사전에 의지하지 않고도 리스트에서 항목을 찾을 수 있다. 특히, 리스트가 정렬된 상태라면 데이터를 사전으로 바꾸는 것보다 그냥 간단히 이진 탐색으로 데이터를 찾는 편이 더 효과적이다(사전 탐색의 시간 복잡도가 O(1)이라 O(log n)인 이진 탐색보다 빠르지만, 리스트를 사전으로 변경하는 시간이 O(n)만큼 걸린다. 또한 사전은 같은 이름의 키가 중복되는 것을 허용하지 않는다).

 

또한 bisect 모듈을 이용하면 잘 최적화된 이진 탐색 기법으로 항목을 찾을 수 있을 뿐 아니라 새로운 항목을 추가해도 정렬된 상태를 유지할 수 있다. 추가로, bisect를 사용해 우리가 찾는 원소와 가장 가까운 값을 매우 빠르게 찾을 수 있다. 이런 기능은 비슷한 두 데이터셋을 비교할 때 특히 유용하다.

 

import bisect
import random

def find_closest(haystack, needl):
  # bisect.bisect_left는 haystack에서 needle보다 크거나 같은 첫 번째 값의 위치를 반환 한다.
  i = bisect.bisect_left(haystack, needle)
  if i == len(haystack):
    return i - 1
  elif haystack[i] == needle:
    return i
  elif i > 0:
    j = i - 1
    # 여기서, i번째 값은 needle보다 크므로(반대로 j번째 값은 needle보다 작다)
    # i번째 값과 j번째 값 중 어떤 값이 needle에 가까운지 비교하기 위해
    # 절댓값을 사용할 필요가 없다.
    if haystack[i] - needle > needle - haystack[j]:
      return j
  return i

important_numbers = []
for i in range(10):
  new_number = random.randint(0, 1000)
  bisect.insort(important_numbers, new_number)


# bisect.insort로 추가했기 때문에 important_numbers는 정렬된 상태로 추가되었다.
print("Haystack: ", important_numbers)

closest_index = find_closest(important_numbers, -250)
print("Closest value to -250: ", important_numbers[closest_index])

closest_index = find_closest(important_numbers, 500)
print("Closest value to 500: ", important_numbers[closest_index])

closest_index = find_closest(important_numbers, 1100)
print("Closest value to 1100: ", important_numbers[closest_index])

bisect모듈을 이용해서 가까운 값 찾기

 

3.2. 리스트와 튜플

튜플은 파이썬 런타임에서 캐싱하므로 사용할 때마다 커널에 메모리를 요청하지 않아도 된다.

리스트와 튜플 모두 다른 타입을 섞어 쓸 수 있다.

 

# 파이썬 3.5의 리스트 크기 할당 방정식
M = (N >> 3) + (N < 9 ? 3 : 6)

N,	0,	1-4,	5-8,	9-16,	17-25,	26-35,	36-46,	...,	991-1120
M,	0,	4,		8,		16,		25,		35, 	46, 	...,	1120

CPython 소스 코드인 Objects/listobject.c의 list_resize() 함수를 참조하자.

 

크기가 20 이하인 튜플은 즉시 회수하지 않고 나중을 위해 저장해둔다. 이 말은 같은 크기의 튜플이 나중에 다시 필요해지면 운영 체제로부터 메모리를 새로 할당받지 않고, 기존에 할당해둔 메모리를 재사용한다는 뜻이다.