탐구 원인
코딩테스트 문제를 풀다보면 내가 작성한 코드의 시간복잡도를 고려하며 코드를 작성하게되는데
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
이 문제를 풀던 중 같은 로직을 가졌지만 함수를 사용했느냐 사용하지 않았느냐로 통과 여부가 바뀌는 것을 확인했다.
정확한 이유를 몰랐던 것과 로직을 엄청 수정해가며 사용한 시간이 아까워 원리를 찾아보기로 했다.
차이점
Why does Python code run faster in a function?
def main(): for i in xrange(10**8): pass main() This piece of code in Python runs in (Note: The timing is done with the time function in BASH in Linux.) real 0m1.841s user 0m1....
stackoverflow.com
역시 나와 같은 궁금증을 가진 사람이 있었고 답변을 읽어보니,
C 언어를 이용하여 Python을 구현하는 CPython은 Python의 코어를 담당하고, 인터프리터가 bytecode로 컴파일된다.
함수가 컴파일 되면서 로컬 변수가 "고정 크기" 배열에 저장되어 시간이 단축된다는 원리였다. 예시로 함수안에 단순 for문을 반복한다면 FOR_ITER opcode를 호출하고 loop를 돌때마다 FOR_ITER 이후 STORE_NAME opcode가 올것이라고 예측하여 STORE_FAST opcode를 호출하여 FOR_ITER + STORE_NAME opcode를 하나의 STORE_FAST opcode로 작동하게 된다. 하지만 global 변수를 사용할 경우 Python은 예측을 하지 않고 opcode를 호출한다고 한다.
따라서 함수를 사용할때 global 변수를 따로 선언하지 않으면 STORE_FAST opcode를 사용하여 속도가 더 빠를것이다. 라는 결론에 도달했다. 이론적으로만 접근해보니 크게 와닿지 않는 것 같아서 직접 코드를 작성해봤다.
from time import time
def func():
s_time = time()
for _ in range(10 ** 7):
continue
return time() - s_time
print( '='*5, 'Not In Function', '='*5)
s_time = time()
for _ in range( 10 ** 7):
continue
print(time() - s_time)
print( '='*5, 'In Function', '='*5)
print(func())
실행 결과 약 2.5배의 차이가 발생했다. 여러번 테스트를 해도 비슷한 차이가 유지되었다.
마치며
함수 사용 유무에 따라 이렇게나 많은 시간 지연이 발생한다는 것을 몸소 느끼면서 코딩테스트 문제를 풀때는 최대한 함수로 묶어서 연산을 시켜야 될 것 같다. 인구 이동 문제 덕분에 새로운 지식을 또 얻게되었다.