[python] 모듈과 라이브러리를 활용해야 하는 이유 (feat.백준 최대힙)
Python은 편하지만 느리다.
Python은 정말 느리다. 정말 정말 느리다.
하지만 편하고 쉽다.
특히 List 자료형은 매우 쉽고 편하다.
당연히 그만큼 많은 리소스를 사용하고, 느린 편이다.
리스트를 잘 활용하면 stack, queue는 물론, tree, heap, 연결 리스트, 해시 테이블 등등등…
수많은 고급 자료형도 어렵지 않게 구현할 수 있다.
다만 알고리즘을 풀 때든, 개발을 할 때든 직접 구현을 하진 않는다.
시간도 시간이지만 가독성과 성능이 굉장히 떨어진다.
stack이나 queue가 필요할 때는 collections의 deque를
heap이 필요할 때는 그냥 heap을 import하면 된다.
해시 테이블은 dict로 구현되어 있다.
그런데 하남자 같잖아
물론 농담이다.
나는 어떤 자료형이나 알고리즘을 쓸 때
내부가 어떻게 굴러가는지 모르는 채로 모듈이나 라이브러리 가져와 쓰고 싶진 않았다.
Tree든, Queue든, heap이든, 직접 구현해서 쓰고 싶었다.
나는 이게 아직도 맞다고 생각한다.
근데 그럴 거면 Python이 아니라 C++을 썼어야지.
안 그래도 느린 파이썬으로 자료구조와 동작들을 하나하나 구현하면
어지간해선 알고리즘 저지 사이트의 시간제한을 맞추지 못한다.
알고리즘 문제를 풀 때는 꼭 모듈이나 라이브러리를 들고 오자.
Python은 기본 구현체가 C다.
그래서 Python을 굳이 분류해서 말하면 CPython이라 표현한다.
(Java의 Jython, C++의 Pyston, Python(!?)과 JIT 컴파일을 활용하는 PyPy 등, 여러 구현체가 있다.)
어쨋든 C로 시작했기 때문에
기본적인 함수와 자료구조, 내부 라이브러리 및 유명 외부 라이브러리들은
C로 구현된 경우가 매우 많다.
이전에 find()함수를 python으로 직접 구현한 탓에 시간을 맞추지 못했다. 백준 - ioioi [SILVER 1]
python의 매우 low한 부분을 건드릴 수 있는 수준이 아니라면 대부분의 경우에 이런 일이 발생한다.
직접 퀵정렬을 구현해도 .sort() 메서드보다 빠르지 않을 것이다.
해시 테이블을 아무리 잘 만들어도 dict 타입보다 느리고 불편할 것이다.
하물며 heap을 직접 구현해도 heapq를 가져와 쓰는 것보다 느리다.
직접 구현한 최대 힙 vs heapq 모듈 가져오기
최대 힙을 ‘구현’만 하면 끝나는 문제다.
즉, import heapq하면 끝난다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq
oper = [int(input()) for _ in range(int(input()))]
Q = []
for o in oper:
if not o:
if Q:
print(-heapq.heappop(Q))
else:
print(0)
else:
heapq.heappush(Q, -o)
한줄 풀기도 가능하나, 굳이 그러진 말자…
위의 방법에서는 110ms 정도가 소요되었다.
이러한 문제에서 heap을 직접 구현해서 쓰면 어지간해선 시간 초과가 발생한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def h_pop(Q):
p = Q[1]
Q[1] = Q[-1]
Q.pop()
i = 1
while i*2 < len(Q):
lc, rc = i*2, i*2+1
if lc == len(Q)-1:
if Q[i] < Q[lc]:
Q[i], Q[lc] = Q[lc], Q[i]
return Q, p
if Q[i] <= Q[lc] or Q[i] <= Q[rc]:
c = lc if Q[lc] > Q[rc] else i*2 + 1
Q[i], Q[c] = Q[c], Q[i]
i = c
else:
return Q, p
return Q, p
def h_push(Q, n):
Q.append(n)
i = len(Q) - 1
while i > 1:
if Q[i] >= Q[i//2]:
Q[i], Q[i//2] = Q[i//2], Q[i]
i = i//2
return Q
oper = [int(input()) for _ in range(int(input()))]
Q = [0]
for o in oper:
if not o:
if len(Q) == 1:
print(0)
else:
Q, n = h_pop(Q)
print(n)
else:
Q = h_push(Q, o)
위의 코드는 시간 초과가 발생한다.
물론 이보다 훨씬 효율적인 방법으로 heap을 구현하여 시간을 감소시킬 수는 있겠으나,
파이썬 상의 구현이라는 한계로 인해 절대 기본 모듈 이상의 성능을 낼 수 없다.
여담으로, global scope에 선언된 Q를 함수에서 참조하는 방법보다
함수에 파라미터로 Q(heap)을 넣고 반환받는 편이 효율적이다.
두 코드의 실제 실행 시간 차이
문제의 최대 조건으로 설정하여 두 코드를 비교해보았다.
N은 100,000으로, 요소는 0 또는 1부터 231까지의 수 중에 하나로 채워넣었다.
실행 시간은 다음과 같았다.
| heapq 모듈 사용 | Python 직접 구현 |
|---|---|
| 33ms | 134ms |
보다시피, 거의 4배 정도 차이가 난다.
물론 heap과 관련된 연산만 있는 게 아니라
여러 조건 분기 연산도 있을 테니 순수하게 모듈과 직접 구현의 차이라 보기 힘들지만
백준에 문제를 제출할 때 이 정도 차이가 날 수 있다는 것 정도는 알 수 있다.
직접 구현도 좋지만, 확실히 알고리즘을 이해한다면
그냥 거인의 어깨 위에 서기로 하자!