[Python] Tip - 내장 알고리즘과 자료구조

많은 데이터를 처리하는 파이썬 프로그램을 구현하다 보면 결국 사용자가 작성한 코드의 알고리즘 복잡도 때문에 속도가 떨어지는 현상을 보게 됩니다. 이는 보통 파이썬 언어의 속도 때문에 생기는 결과가 아닙니다. 이런 문제는 최적의 알고리즘과 자료구조를 사용하지 않아서 일어났을 가능성이 더 큽니다.

속도 이외에도 공통 알고리즘과 자료구조를 사용하면 좀 더 편해집니다.

더블 엔디드 큐

collections 모듈의 deque 클래스는 더블 엔디드 큐(double-ended queue)입니다. deque는 큐의 처음과 끝에서 아이템을 삽입하거나 삭제할 때 항상 일정한 시간이 걸리는 연산을 제공합니다. 이와 같은 기능은 선입선출(FIFO, First-In-First-Out) 큐를 만들 때 이상적입니다.

from collections import deque fifo = deque() fifo.append(1) # 생산자 print(fifo) x = fifo.popleft() # 소비자 print(x) # 결과 # deque([1]) # 1

내장 타입 list도 큐와 마찬가지로 순서가 있는 아이템 시퀀스를 담습니다. 일정한 시간 내에 리스트의 끝에서 아이템을 삽입하거나 삭제할 수 있습니다. 하지만 리스트의 시작 부분에서 아이템을 삽입하거나 삭제하는 연산에는 선형적 시간(linear time - 횟수에 따라 시간도 늘어남)이 걸리므로 deque의 일정한 시간보다 훨씬 느립니다.

정렬된 딕셔너리

표준 딕셔너리는 정렬되어 있지 않습니다. 즉, 같은 키와 값을 담은 dict를 순회해도 다른 순서가 나올 수 있다는 의미입니다. 이런 돈작은 딕셔너리의 빠른 해시 테이블을 구현하는 방식이 만들어낸 뜻밖의 부작용입니다.

import random a = {} a['foo'] = 1 a['bar'] = 2 while True: z = random.randint(99, 1013) b = {} for i in range(z): b[i] = i b['foo'] = 1 b['bar'] = 2 for i in range(z): del b[i] if str(b) != str(a): break print(a) print(b) print('Equal?', a == b) # 결과 # {'foo': 1, 'bar': 2} # {'bar': 2, 'foo': 1} # Equal? True

collections 모듈의 OrderedDict 클래스는 키가 삽입된 순서를 유지하는 특별한 딕셔너리 타입입니다. OrderedDict의 키를 순회하는 것은 예상 가능한 동작입니다. 따라서 모든 코드를 확정하고 만들 수 있으므로 테스팅과 디버깅을 아주 간단하게 할 수 있습니다.

from collections import OrderedDict a = OrderedDict() a['foo'] = 1 a['bar'] = 2 b = OrderedDict() b['foo'] = 'red' b['bar'] = 'blue' for value1, value2 in zip(a.values(), b.values()): print(value1, value2) # 결과 # 1 red # 2 blue

기본 딕셔너리

딕셔너리는 통계를 관리하고 추적하는 작업에 유용합니다. 딕셔너리를 사용할 때 한 가지 문제는 어떤 키가 이미 존재한다고 가정할 수 없다는 점입니다. 이 문제 때문에 딕셔너리에 저장된 카운터를 증가시키는 것처럼 간단한 작업도 까다로워집니다.

stats = {} key = 'my_counter' if key not in stats: stats[key] = 0 stats[key] += 1

collections 모듈의 defaultdict 클래스는 키가 존재하지 않으면 자동으로 기본값을 저장하도록 하여 이런 작업을 간소화합니다. 할 일은 그저 키가 없을 때마다 기본값을 반환할 함수를 제공하는 것뿐입니다. 다음 예제에서 내장 함수 int는 0을 반환합니다.

from collections import defaultdict stats = defaultdict(int) stats['my_counter'] += 1 print(stats) # 결과 # defaultdict(<class 'int'>, {'my_counter': 1})

힙 큐

힙(heap)은 우선순위 큐(priority queue)를 유지하는 유용한 자료 구조입니다. heapq모듈은 표준 list 타입으로 힙을 생성하는 heappush, heappop, nsmallest 같은 함수를 제공합니다.

임의의 우선순위를 가지는 아이템을 어떤 순서로도 힙에 삽입할 수 있습니다.

import heapq a = [] heapq.heappush(a, 5) heapq.heappush(a, 3) heapq.heappush(a, 7) heapq.heappush(a, 4) # 가장 우선순위가 높은 것(가장 낮은 수)부터 제거 print(heapq.heappop(a), heapq.heappop(a), heapq.heappop(a), heapq.heappop(a)) # 결과 # 3 4 5 7

결과로 만들어지는 list를 heapq 외부에서도 쉽게 사용할 수 있습니다. 힙의 0인덱스에 접근하면 항상 가장 작은 아이템이 반환됩니다.

import heapq a = [] heapq.heappush(a, 5) heapq.heappush(a, 3) heapq.heappush(a, 7) heapq.heappush(a, 4) assert a[0] == heapq.nsmallest(1, a)[0] == 3 # 같음 print('Before:', a) a.sort() print('After:', a) # 결과 # Before: [3, 4, 7, 5] # After: [3, 4, 5, 7]

이러한 각 heapq 연산에 걸리는 시간은 리스트의 길이에 비례하여 로그 형태로 증가합니다. 표준 파이썬 리스트로 같은 동작을 수행하면 시간이 선형적으로 증가합니다.

바이섹션

list에서 아이템을 검색하는 작업은 index 메서드를 호출할 때 리스트의 길이에 비례한 선형적 시간이 걸립니다.

x = list(range(10**6)) i = x.index(991234)

bisect_left 같은 bisect 모듈의 함수는 정렬된 아이템 시퀀스를 대상으로한 효율적인 바이너리 검색을 제공합니다. bisect_left가 반환한 인덱스는 시퀀스에 들어간 값의 삽입 지점입니다.

import bisect x = list(range(10**6)) i = bisect.bisect_left(x, 991234)

바이너리 검색의 복잡도는 로그 형태로 증가합니다. 다시 말해 아이템 백만 개를 담은 리스트를 bisect로 검색할 때 걸리는 시간은 아이템 14개를 담은 리스트를 index로 순차 검색할 때 걸리는 시간과 거의 같습니다.

이터레이터 도구

내장모듈 itertools는 이터레이터를 구성하거나 이터레이터와 상호 작용하는 데 유용한 함수를 다수 포함합니다.

itertools에 있는 함수는 세 가지 주요 카테고리로 나뉩니다.

이터레이터 연결

• chain: 여러 이터레이터를 순차적인 이터레이터 하나로 결합
• cycle: 이터레이터의 아이템을 영원히 반복
• tee: 이터레이터 하나를 병렬 이터레이터 여러 개로 나눔
• zip_longest: 길이가 서로 다른 이터레이터들에도 잘 동작하는 내장 함수 zip의 변현

이터레이터에서 아이템 필터링

• islice: 복사없이 이터레이터를 숫자로된 인덱스로 슬라이스
• takewhile: 서술 함수(predicate function)가 True를 반환하는 동안 이터레이터의 아이템을 반환
• dropwhile: 서술 함수가 처음으로 False를 반환하고 나면 이터레이터의 아이템을 반환
• filterfalse: 서술 함수가 False를 반환하는 이터레이터의 모든 아이템을 반환. 내장 함수 filter의 반대 기능을 함

이터레이터에 있는 아이템들의 조합

• product: 이터레이터에 있는 아이템들의 카테시안 곱을 반환. 깊게 중첩된 리스트 컴프리헨션에 대한 훌륭한 대안
• permutations: 이터레이터에 있는 아이템을 담은 길이 N의 순서 있는 순열(permutations)을 반환
• combinations: 이터레이터에 있는 아이템을 중복되지 않게 담은 길이 N의 순서 없는 조합(combinations)을 반환

여기서 설명하지 않은 itertools 모듈의 기능과 사용 방법이 많습니다. 까다로운 이터레이션 코드를 다루는 상황이라면 itertools 문서를 다시 살펴보고 쓸만한 기능이 있는지 찾아볼 가치가 있습니다.

요약

알고리즘과 자료구조를 표현하는 데는 파이썬의 내장 모듈을 사용 이 기능들을 직접 재구현하는 것은 어려움