들어가기 전에
잘못된 부분 지적은 언제나 환영입니다!
파이썬은 코테용으로만 쓰고 있기 떄문에 실제 개발과는 다를 수 있습니다.
문제 제기
프로그래밍을 배울 떄, 반복되거나 의도가 명확히 보이지 않는 부분은 함수를 만들어 분리하란 말을 들었을 것이다.
https://www.acmicpc.net/problem/1600 을 Python3로 해결하는 과정에서
범위 이탈 검증에 대한 부분을 함수로 분리하니 시간초과를 받게 됐다.
함수 호출에 대해 비용이 생기는 것은 알고 있지만 생각보다 비용이 커서 여기에 대해 알아보게됐다.
문제의 코드 (outRange 함수를 보면 된다.)
from collections import deque
def outRange(thereX, thereY, W, H):
if 0 <= thereX <= W and 0 <= thereY <= H:
return False
return True
K = int(input())
W, H = map(int, input().split())
board = [input().split() for h in range(H)]
visit = [[-1 for w in range(W)] for h in range(H)]
W, H = W - 1, H - 1
Mir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
Hir = [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]
answer = -1
q = deque([(0, 0, 0, K)])
while q:
hereX, hereY, hereC, hereK = q.popleft()
if hereX == W and hereY == H:
answer = hereC
break
if hereK >= 1:
for h in Hir:
thereX, thereY = hereX + h[0], hereY + h[1]
if outRange(thereX, thereY, W, H) or board[thereY][thereX] == '1':
continue
if visit[thereY][thereX] < hereK - 1:
visit[thereY][thereX] = hereK - 1
q.append((thereX, thereY, hereC + 1, hereK - 1))
for m in Mir:
thereX, thereY = hereX + m[0], hereY + m[1]
if outRange(thereX, thereY, W, H) or board[thereY][thereX] == '1':
continue
if visit[thereY][thereX] < hereK:
visit[thereY][thereX] = hereK
q.append((thereX, thereY, hereC + 1, hereK))
print(answer)
시간 측정
10 ^ 8번 도는 loop에서 짝수인 경우, 1을 더하는 코드의 시간이다.
여기서 짝수 검증을 함수로 분리한 경우, 안 한 경우로 나눴다.
from time import time
def function(n):
if n % 2 == 0:
return True
return False
def main():
n = 0
print("------ only main ------")
start = time()
for i in range(10 ** 8):
if n % 2 == 0:
n += 1
print(time() - start)
print("------ use function ------")
n = 0
start = time()
for i in range(10 ** 8):
if function(n):
n += 1
print(time() - start)
if __name__ == "__main__":
main()
속도에 대한 결과는 아래 사진과 같다.
only main부분 수행 후, 캐시로 인해 불확실한 결과가 나올 수 있기에
캐시를 민 후, 순서를 바꾼 결과를 그 아래 추가했다.
과연 다른 언어도 이렇게 차이가 날까?
Java 코드로 바꿔 실행한 결과다
public class main {
public static void main(String[] args) {
int x = 0;
long start;
start = System.currentTimeMillis();
for (long i = 0; i <= 100000000; i++) {
if (i % 2 == 0) {
x += 1;
}
}
System.out.println("only main " + (System.currentTimeMillis() - start) / 1000.0);
x = 0;
start = System.currentTimeMillis();
for (long i = 0; i <= 100000000; i++) {
if (function(i)) {
x += 1;
}
}
System.out.println("use function : " + (System.currentTimeMillis() - start) / 1000.0);
}
public static boolean function(long i) {
if (i % 2 == 0)
return true;
return false;
}
}
파이썬과는 다르게 함수 호출이 있고 없고 차이가 별로 없단 것을 알 수 있다.
바이트 코드 분석
위에가 main, 아래가 function에 대한 바이트 코드이다.
짝수 검증을 하는 과정에서 함수 호출을 하지 않는 경우 opcode가 LOAD_FAST,
외부 함수를 호출하는 경우 opcode가 LOAD_GLOBAL인 것을 볼 수 있다.
LOAD_GLOBAL의 역할
global dict table에서 호출하려는 Identifer에 대한 정보를 가져온다.
그리고 파이썬 코드를 실행하기 위해선 내부적으로 많은 모듈들이 실행된다.
그만큼 테이블엔 많은 함수들의 정보가 있어 원하는 Identifier를 찾으려면 O(logN)의 시간이 소모된다.
log의 시간 복잡도를 가지기 때문에 호출 횟수가 엄청 크지 않은 이상 성능에 큰 영향을 주지 않는다.
하지만, 찾는 횟수가 지나치게 많다면 성능에 지장을 준다. 그리고 여기서 개인적인 궁금함이 생겼다.
캐시가 도움을 줄 수 없는 건가?
dict table이 많은 정보를 갖고 있는 만큼 원하는 Identifer를 찾기 위해선 일정 비용이 소모된다는 것은 이해할 수 있다.
하지만, 이 코드에선 하나의 함수에 대한 Identifer를 찾는 것이고, 단기간에 자주 호출되는 만큼 해당 부분에 대해선
캐시 테이블에 등록이 됐을 거라고 생각한다.
초기 접근에선 O(logN)만큼 시간이 소모되더라도, 캐시 테이블에 등록되면 상수 시간에 처리될 거라 생각한다.
이렇게 되면 함수 호출에 대한 비용은 그렇게 크지 않을 것이다.
여기에 대해 좀 더 찾아본 결과 호출 뿐만이 아니라, 매개변수 전달 방식에서도 문제가 있었다.
Monkey Patch
간단하게 런타임에 클래스나 모듈의 속성을 동적으로 대체하는 행위다.
다르게 말하면 프로그램이 추상적이게 된다.
즉, 실체화 하기 위한 비용이 발생한다.
C나 JAVA같은 경우엔 타입 검사나 syntax에 대해 엄격한 편이므로 일반적으로 이러한 행위는 허용되지 않는다.
이런 부분이 엄격하단 것은 프로그램의 안정성이 증가하고
프로그램의 안정성이 증가하는 것은 데이터에 대해 추가적으로 검증할 필요가 적어지기 때문에
성능 향상에도 도움이 된다.
하지만, python같이 유연한 언어인 경우 엄격한 검사가 힘들어지기 때문에
부족한 부분을 런타임 영역에서 해결해야 하니, 프로그램 실행 속도가 느려진다.
우리가 파이썬은 속도가 느리다고 하는 이유가 바로 이거 때문이다.
Monkey Patch에 대한 파이썬 예시 코드다.
def bar(text = 1):
if text == 1:
print("ONE!")
else:
print("NOT ONE!")
bar("c") # 출력 : NOT ONE!함수에 대한 매개변수 타입은 int형인데
함수에 대한 인자는 문자열 c인 것을 볼 수 있다.
C나 Java라면 타입 체커에서 에러를 반환하지만
파이썬에선 이 Monkey Patch 때문에 에러 없이 실행된다.
원래 bar의 매개변수는 int형이지만, 런타임에선 bar("c")로 인해 매개변수 타입이 string으로 바뀌게 된다.
다르게 말해서, 함수의 매개변수가 추상적이니, 런타임 때 함수가 호출 되면 이 추상화를 실체화 해야 한다.
그렇기 때문에, 함수가 자주 호출되고, 매개변수가 많을 수록 함수 호출에 대한 비용은 점점 증가한다.
매개변수 전달 방식 외에도 Monkey Patch가 사용된 부분은 많지만, 거기에 대해선 다루지 않는다.
그럼 함수 분리 없이 main에서만 코드를 짜야 하나?
본문에서 말했듯이, 호출 횟수가 엄청 크지 않는 이상 눈에 띄는 성능 저하는 일어나지 않는다.
다만, 특정 기능을 빠르고 반복적으로 수행해야 하는 상황이 많은 코딩 테스트같은 경우
함수를 반복적으로 호출하는 것 보단 반복이 가능한 함수를 만드는 게 좋다.
쉽게 말해서 repeat는 지양하고, iterable을 지향하면 된다.
결론
시간 초과가 발생하는 경우, 너무 반복적으로 호출되는 함수가 있는지를 확인할 필요가 있다.
함수를 분리할 땐, 이 함수 내부에서 반복적인 일을 얼마나 수행할 수 있는지를 고려하면
적은 비용으로 코드를 깔끔하게 분리할 수 있다.
Reference
https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
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
https://stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive
Why is a function/method call in python expensive?
In this post, Guido van Rossum says that a function call may be expensive, but I do not understand why nor how much expensive can be. How much delay adds to your code a simple function call and why?
stackoverflow.com
https://8iggy.tistory.com/155?category=1014608
Python 함수 코드가 일반 코드보다 빠른 이유
읽기 전 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다. 개인적으로 사용해보면서 배운 점을 정리한 글입니다. 문제 제기 알고리즘 문제를 풀다보면 항상 시간 제약에 민
8iggy.tistory.com
https://stackoverflow.com/questions/5626193/what-is-monkey-patching
What is monkey patching?
I am trying to understand, what is monkey patching or a monkey patch? Is that something like methods/operators overloading or delegating? Does it have anything common with these things?
stackoverflow.com