Python은 느리다. 그렇기 때문에 Python에 대한 이해도에 따라 코드의 성능이 크게 차이 날 수 있다. 이 번 글에서는 Python의 속도를 향상할 수 있는 방법에 대해 적어보려 한다. 이 글은 각각의 개념에 대해 상세하게 설명하지 않는다. 대신 왜 성능에 문제가 발생하고, 어떻게 해결할 수 있는지에 초점을 두고 작성하였다.
- JIT 활용
- 내장 함수 활용
- Generator로 메모리 아끼기
- for / while보다 빠른 반복
- dictionary와 set으로 조회
- 내장 모듈의 자료구조
- 빠르게 문자열 합치기
- 빠른 입출력
- global 참조 피하기
- dot 줄이기
- 불필요한 연산, 호출 줄이기
Python은 간결하고 명확한 코드 작성을 지향한다. 위 방법 중 일부 표현은 파이썬스럽(Pythonic)지 않을 수 있으며, 상황에 따라 권장되지 않을 수 있다. 다만, 일시적으로 코드를 사용하는 경우 또는 순간적인 성능 향상이 중요한 경우 위 방법들은 매우 도움이 된다. 즉, 이 글에서 소개하는 트릭은 코딩 테스트를 위해 사용하는 방법일 뿐, '항상 옳은' 방식은 아님을 인지하고 있어야 한다.
JIT 활용
JIT는 Just-In-Time의 약자이다. Python은 인터프리터를 통해 해석된다. 쉽게 말해 컴퓨터가 Python 코드를 바로 이해하는 것이 아니라 중간에 통역사를 거쳐 이해하고 실행한다. 이러한 Python의 구조가 속도를 느리게 만든다. 하지만 JIT는 런타임에 코드를 컴파일한다. 간단히 말해, 여려 번 재사용되는 코드가 있다면 컴퓨터가 이해할 수 있는 형식으로 변환한 후, 다음번에 요청했을 때 인터프리터를 거치지 않고 바로 이해하고 실행한다.
가장 쉽게 JIT를 적용하는 방법은 Pypy를 이용하는 것이다. 백준의 경우, [ Python3 ]와 [ Pypy3 ] 2가지 옵션을 제공한다. 이 때 Pypy3를 선택하고 제출하면 된다. Pypy가 대부분의 경우 더 빠르지만 항상 Pypy가 빠른 것은 또 아니다.
내장 함수 활용
Python은 기본적으로 다양한 내장 함수를 제공한다. 그리고 이 함수들은 C로 작성되었다. 같은 코드를 Python 위에서 실행하는 것보다 전문가들이 C로 만든 내장 함수를 활용하는 것이 더 빠르다.
- Built-in-Functions: https://docs.python.org/ko/3/library/functions.html
- 유용한 함수: all, any, divmod, enumerate, filter, isinstance, len, map, max, min, range, reversed, sorted, sum, zip
뭔가 많아 보이겠지만 코테에서 충분히 사용할 법한 함수들이다. 이 중 일부는 아래에서 자세하게 소개할 것이다.
Generator로 메모리 아끼기
Generator를 몰라도 걱정할 필요 없다. 비유를 하자면, Generator를 사용하지 않는다는 건 필요한 도구를 바닥에 다 펼쳐두고 사용하는 것이다. 하지만 generator를 사용한다는 건 도구가 필요할 때마다 서랍에 꺼내 쓰는 것이다. 쉽게 말해, generator를 사용하면 공간을 아낄 수 있다. 익히 아는 range( )도 generator를 생성한다.
Generator를 알고 있는 사람이라면 yield 키워드를 떠올리겠지만, Comprehension을 활용하면 훨씬 쉽게 정의할 수 있다.
# Generator Comprehension
even = (n*2 for n in range(100))
# 사용법
for i in even:
print(i)
Generator에 대해 알고 싶다면 아래 글을 참고하자.
제너레이터(Generator)를 활용한 코루틴(coroutine)
제너레이터는 Python 객체의 한 종류로 게으르기 때문에 효율적으로 메모리를 사용할 수 있도록 해준다. (정보를 한 번에 모두 가져오지 않고 정보가 필요할 때 조금씩 불러오는 것을 lazy하다고
denev6.tistory.com
for / while 보다 빠른 반복
Python 위에서 동작하는 반복문은 당연히 C 위에서 반복하는 것보다 느리다.
1. Comprehension 활용하기
[i*2 for i in range(100)] # -> list
(i*2 for i in range(100)) # -> generator생각보다 많은 사람들이 Generator Comprehension에 대해 잘 모르고 있다. 단순히 [ ]로 감싸면 list, ( )로 감싸면 generator를 반환한다. 만약 단순 반복이 목적이라면 ( )를 활용할 수 있다. 하지만 list 객체의 메서드를 활용하거나 직접 list를 조작해야 한다면 [ ]를 사용하면 된다.
2. map, filter
map과 filter는 위에서도 소개했던 Python 내장 함수 중 하나이다.
# map
a = map(int, ["3", "7", "9"])
a = list(a)
# map을 for문으로 작성하면
a = []
for n in ["3", "7", "9"]:
a.append(int(n))
# filter
a = filter(lambda x: x%2==0, [2, 5, 6, 9])
a = list(a)
# filter를 for문으로 작성하면
a = []
for n in [2, 5, 6, 9]:
if n % 2 == 0:
a.append(n)- map: 함수를 입력받아 모든 값에 대하여 함수를 적용해준다.
- filter: 모든 값 중 조건(true를 반환하는 함수)에 해당하는 값만을 반환한다.
dictionary와 set으로 조회
일반적으로 값을 list에 많이 저장하지만 list는 값을 찾기 위해 처음부터 끝까지 하나씩 살펴본다. 따라서 O(N) 시간이 소요된다. 대신 dictionary는 O(1)로 한 번에 값을 조회할 수 있다. 이는 Dictionary가 Hash Table이라는 구조를 사용하기 때문이다.
Dictionary는 key-value 형태로 맵핑되어 있는 한 쌍의 데이터를 저장한다. 만약 단일 데이터의 조회가 목적이라면 set을 사용할 수 있다. set은 '집합'이라는 개념으로 추상화되어 있지만, 실질적으로 key만 있는 dictionary라고 생각하면 된다. dictionary의 key와 같이 순서가 없고, 중복이 없다. 값을 조회하는 시간도 O(1)로 동일하다.
내장 모듈의 자료구조
Python은 자체적으로 완성도 높은 자료구조를 제공한다. 이것들은 코테에서 매우 유용하게 사용된다.
대표적으로 deque, Counter, defaultdict 등이 있다. 특히 deque는 Python으로 코테를 한다면 몰라서는 안 되는 자료구조이다. 상황에 따라 list에 비해 효율적으로 값을 저장하고 제거할 수 있기에 많이 사용된다.
자세한 내용은 공식문서를 살펴보자.
collections — Container datatypes
Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.,,...
docs.python.org
빠르게 문자열 합치기
Python은 f-string이라고 하는 아주 매력적인 포맷팅 기능을 가지고 있다.
res = 33
f"RES: {res}"f-string은 가독성이 좋은 뿐만 아니라 성능도 뛰어나다. 만약 섬세한 포맷팅 없이 문자를 이어 붙이는 것이 목적이라면 Join으로 간단하게 처리할 수 있다.
"\n".join(["1st", "2nd", "3rd"])
" ".join(map(str, [1, 2, 3]))코테에서 결과를 줄 바꿈으로 출력하거나 한 칸씩 띄워서 한 줄에 출력하라는 형식의 문제들이 많다. 그럴 때마다 Join이 유용하게 사용된다.
빠른 입출력
import sys
sys.stdin.readline() # 입력
sys.stdout.write() # 출력input, print 대신 sys 모듈을 불러와 readline과 write로 각각 입출력을 할 수 있다. Python은 함수 자체를 변수에 저장할 수 있기 때문에 아래와 같이 작성할 수 있다.
import sys
# 정의
input = sys.stdin.readline
print = sys.stdout.write
# 실행
input().rstrip("\n")
print()하지만 일반 input, print 함수와 차이점이 있기 때문에 주의해야 한다. readline은 끝에 줄 바꿈('\n')까지 읽어온다. 따라서 strip을 통해 '\n'을 제거해야 우리가 아는 input과 동일하게 사용할 수 있다. print는 모든 타입의 데이터를 받지만 write는 문자열만을 출력한다. 따라서 다른 타입의 데이터가 있다면 문자열로 변경 후 출력해야 한다. 이때 위에서 봤던 f-string이나 join을 활용하면 아주 효율적으로 출력이 가능해진다.
import sys
print = sys.stdout.write
res = [3, 7, 1, 9]
print(" ".join(map(str, res))) # 3 7 1 9
print(res) # 오류Global 참조 피하기
global을 통해 전역 변수를 참조하게 되면 성능이 저하될 수 있다. global은 단순히 성능에 영향을 줄 뿐만 아니라 예상치 못한 오류를 발생시킬 수 있기 때문에 일반적인 코드에서도 지양된다. global 값을 참조해야 하는 상황이라면 함수 파라미터로 값을 전달하거나 OOP로 설계하는 등 대안을 사용하는 것이 안전하다고 생각한다.
dot 줄이기
dot은 클래스에 접근하거나 패키지에 접근할 때 사용하는 .를 이야기한다. 아주 사소한 부분이지만 성능에 영향을 줄 수 있는 요소이다.
class Count():
def __init__(self):
self._n = 0
def count1(self, nums: list):
# dot 여러번 사용
for i in nums:
self._n += i
def count2(self, nums: list):
# dot 2번만 사용
n = self._n
for i in nums:
n += i
self._n = n이렇게 작성하는 것이 파이썬다운 방식인지에 대해서는 의문이다. 다만 속도 향상에 도움이 된다면 시도해 볼 수 있다.
# Bad
import math
math.sqrt()
# Good
from math import sqrt
sqrt()모듈 전체를 불러와 사용하면 성능에 문제가 될 수 있다. 또한 대부분의 경우, 구체적인 함수를 불러와 사용하는 것이 가독성을 높여준다.
불필요한 연산, 호출 줄이기
코드를 살펴보며 불필요한 값을 저장하지 않았는지, 불필요한 연산이 함께 수행되지 않았는지 살펴보자. 아무리 Python 코드를 최적화한다 하더라도 사용한 자료구조/알고리즘이 효율적이지 못하면 C++로 풀어도 시간 초과가 난다.
또한 Python은 매우 유연한 언어이다. 다른 언어로는 몇십 줄이 걸릴 문제를 단 몇 줄만으로 해결해 버린다. 어떤 사람은 한 줄에 모든 코드를 밀어 넣어 단 한 줄로 문제를 풀어버리기도 한다. 여기서부터는 파이썬다운 코드를 벗어나는 영역이다. 하지만 효율성이 중요한 코테에서는 충분히 합리적인 코드가 될 수 있다. 그리고 결과적으로 성능도 잘 나온다.