[Python] 모듈과 라이브러리를 활용해야 하는 이유 (feat.백준 최대힙)

Python은 편하지만 느립니다.

Python은 정말 느립니다. 정말 정말 느립니다.

 

하지만 편하고 쉽기 때문에 러닝 커브 낮고 접근성이 매우 높습니다.

 

특히 List 자료형은 매우 쉽고 편합니다.

 

당연히 그만큼 많은 리소스를 사용하고, 느린 편입니다.

 

리스트를 조금만 활용하면 stack, queue는 물론, tree, heap, 연결 리스트, 해시 테이블 등등등...

 

수많은 고급 자료형도 어렵지 않게 구현할 수 있습니다.

 

다만 알고리즘을 풀 때든, 개발을 할 때든 직접 구현을 하진 않습니다.

 

시간도 시간이지만 가독성과 성능이 굉장히 떨어지기 때문이죠.

 

stack이나 queue가 필요할 때는 collections의 deque를

 

heap이 필요할 때는 그냥 heapq를 가져오면 됩니다.

 

해시 테이블 구조는 dict로 구현되어 있습니다.

 

그런데 하남자 같잖아

물론 농담입니다.

 

저는 어떤 자료형이나 알고리즘을 쓸 때

 

내부가 어떻게 굴러가는지 모르는 채로 모듈이나 라이브러리 가져와 쓰고 싶진 않았습니다.

 

Tree든, Queue든, heap이든, 직접 구현해서 쓰고 싶었습니다.

 

물론, 개념과 구조를 이해하기 전까진 매우 좋은 경험이라 생각합니다.

 

개념이 익숙해진 이후에도 굳이 그런 일을 반복하는 것은 별로 좋지 않습니다.

 

그럴 거면 Python이 아니라 C++을 썼어야지.

안 그래도 느린 파이썬으로 자료구조와 동작들을 하나하나 구현하면

 

어지간해선 알고리즘 저지 사이트의 시간제한을 맞추지 못합니다.

 

실제 서비스 개발이면 더더욱 큰 문제입니다.

 

꼭 모듈이나 라이브러리를 들고 옵시다.

---

Python은 기본 구현체가 C입니다.

 

그래서 Python을 굳이 분류해서 말하면 기본이자 메인인 Python은 CPython이라 표현합니다.

 

(Java/Jvm의 Jython, C++의 Pyston, Python(!?)과 JIT 컴파일을 활용하는 PyPy 등, 여러 구현체가 있다.)

 

어쨋든 C로 시작했기 때문에, 기본적인 함수와 자료구조, 모듈 및 유명 외부 라이브러리들은

 

내부 핵심 로직이 C/C++로 구현된 경우가 상당히 많습니다.

 

이전에 find()함수를 python으로 직접 구현한 탓에 시간을 맞추지 못한 적이 있습니다. 백준 - ioioi [SILVER 1]

[Python] 백준 5525 - ioioi

 

python 구조체를 직접 건드릴 수 있는 수준이 아니라면 대부분의 경우에 이런 일이 발생합니다.

 

직접 Tim sort를 구현해도 .sort() 메서드보다 빠르지 않습니다.

 

해시 테이블을 아무리 잘 만들어도 dict 타입보다 느리고 불편합니다.

 

heap을 직접 구현해도 heapq를 가져와 쓰는 것보다 느립니다.

 

직접 구현한 최대 힙 vs heapq 모듈 가져오기

 

백준 - 최대 힙 [SILVER 3]

 

최대 힙을 '구현'만 하면 끝나는 문제입니다.

 

즉, import heapq하면 거의 문제의 반 이상을 해결한 것입니다.

 

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을 직접 구현해서 쓰면 어지간해선 시간 초과가 발생합니다.

 

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)을 넣고 반환받는 편이 효율적입니다.

 

이는 파이썬의 변수 스코프 탐색 룰인 LEGB 룰에 관한 것으로, 따로 이야기 해보도록 하겠습니다.

 

두 코드의 실제 실행 시간 차이

문제의 최대 조건으로 설정하여 두 코드를 비교해보았습니다.

 

N은 100,000으로, 요소는 0 또는 1부터 2³¹까지의 수 중에 하나로 채워넣었습니다.

 

실행 시간은 다음과 같았습니다.

 

heapq 모듈 사용	Python 직접 구현
33ms	134ms

보다시피, 거의 4배 정도 차이가 나는 것을 확인할 수 있습니다.

 

물론 다양한 조건 및 구현 방식에 따라 큰 오차가 발생할 것이겠지만,

 

백준에 문제를 제출할 때 이 정도 차이가 날 수 있다는 것 정도는 알 수 있습니다.

핵심

• 구현된 게 있다면, 모듈과 라이브러리를 가져다 쓰자.