파이썬 알고리즘 관련 시간을 줄이는 팁들

자고로 시간을 줄이는 것은 언제나 알고리즘에 있어 지향해야할 목표점이다. 아직 알고리즘 초보라 편법처럼이라도 시간을 줄이고픈 마음에 팁들이 생길 때마다 추가하려고 한다.

 

입력 - sys 모듈의 readline() 메서드 사용

보통 입력을 받을 때 input() 메서드를 사용하지만, sys 모듈의 readline()을 사용하면 더 빠른 시간에 입력을 받을 수 있으며, 데이터가 많아질 수록 이 차이는 더 커진다.

 

리스트 반복하기 - 곱셈 연산자 사용

파이썬의 기능 중 리스트를 반복할 때 곱셈을 사용할 수 있다는 장점이 있다. 똑같은 데이터를 반복적으로 리스트에 넣고 싶을 때, for 과 in range(n)을 사용할 수도 있지만, 곱셈 연산자를 사용하는 것이 더 빠르다.

 

예) 1억개의 0 넣기

import time

times = 100000000

start = time.time()

# for 과 in, range
i = [0 for _ in range(times)]
mid1 = time.time()
print(mid1-start)

# 곱셈 연산자
i = [0] * times
mid2 = time.time()
print(mid2-mid1)

 

출력

 

6.190709590911865
0.6791272163391113

 

곱셈 연산자가 약 10배 빠른 것을 볼 수 있다.

 

그러나 여러 리스트를 만들 때에는 range 함수를 쓰도록 한다. 이는 리스트를 곱셈으로 만들 때에는 같은 참조를 하는 리스트 객체를 여러 개 만들기 때문에, 각 리스트가 다른 값을 담도록 하게 하고 싶을 때 한 리스트를 바꾸면 다른 모든 곱셈으로 만들어진 리스트들이 바뀌어지게 될 것이다.

 

큐와 우선순위 큐 - 모듈 사용

큐를 구현할 때는 collections 모듈의 deque를 사용하고, 우선순위 큐를 구현할 때는 heapq를 사용하도록 한다.