파이썬 성능 향상 및 주의사항 with PS

파이썬으로 시간초과(TLE) 가 난다면 PyPy 로 제출하라

시간제한에 걸릴정도의 시간복잡도가 아닌데도 시간초과가 뜰때가 꽤 있다.
이럴때는 PyPy3 로 제출해보면 높은 확률로 통과한다.

• 주의점: PyPy 에서는 setrecursionlimit 을 높게 설정하면, 메모리 초과가 뜰수있으니 해당 코드를 지워줘야한다.

파이썬 인터프리터는 default recursion limit 이 작게 설정되어있다.

명시적으로 재귀 깊이 제한을 늘리지않는다면, 매우 얕은 재귀 깊이만 허용된다. 보통 1000 이 기본값이고, 재귀 깊이가 1000을 넘어가면 재귀 제한을 초과했다는 에러를 띄운다. (물론 인터프리터나 언어 버전마다 다를수도 있다. 정확한 제한을 알고싶다면 sys.getrecursionlimit() 함수로 확인해보길 바란다. )

해결책. 재귀 한도를 늘려라

import sys
sys.setrecursionlimit(100000000)

파이썬 인터프리터로 재귀 깊이를 늘리고 싶다면, 위의 코드로 recursionlimit 을 설정해야한다.

주의점 및 추가 설명

• pypy에서 재귀 한도를 별도로 설정하지않아도 되지만, 일정이상 커지면 스택오버플로우가 날수도 있다.
  • 꼭 재귀를 깊이 써야겠다면 파이썬으로 재귀 깊이 한도를 늘려서 제출하는게 최선같다.
  • 하지만.. 꼭 파이썬으로는 불가능하고, pypy로는 가능한 문제가 있는데 이럴때는 차라리 재귀를 쓰지말자..
• 파이썬 3.9 부터는 재귀 한도를 늘리려는것같다 PEP 611 (opens new window)

입력함수로 sys.stdin.readline 을 쓰자

input() 함수는 시간초과가 발생할수도있다. 입력함수를 많이 써야해서 저렇게 긴 함수이름을 타이핑하기 귀찮다면 input 함수를 버리고 sys.stdin.readline 으로 덮어씌워서 사용할수있다.

import sys
input = sys.stdin.readline

시간복잡도를 확인하고 쓰자

큐를 구현하기위해 리스트를 쓰지말자. deque 을 쓰자

리스트의 pop(0) 는 O(n) 시간복잡도라서 큐로 사용하기에는 매우 비효율적이다.
반면 collections.deque 은 큐와 스택의 구현을 위해 만들어진 클래스이므로 pop 연산이 O(1) 로 최적화되어있다. 그래서 deque 을 사용하는것이 합리적인 선택이다.

• Queue 라는 클래스도 있기는 하지만, 이건 멀티스레딩 프로그래밍을 할때나 쓰는 동기화 가능한 큐라서 속도가 떨어진다. PS 에서는 deque 으로 큐를 구현하는게 낫다.

Pythonic 한 코드를 작성하는것이 성능에도 좋다.

내부적으로 최적화된 경우가 많기때문에, 최대한 파이썬 철학에 맞는 코드를 짜는것이 성능상으로도 우수한 경우가 많다.

• list comprehension
• slicing
• ..