[파이썬] Min vs. If, 좀 더 빠르게 (실행시간 정리)

시작하기 전에

본 포스팅은 파이썬 알고리즘 문제풀이 도중 생각난 의문들을 해결하기 위한 정리를 수행한 기록이다.

파이썬은 매우 느린 언어로, 연산자 지정, 함수 호출 여부 등에 따라 실행시간이 TC를 판가름할 정도로 천차만별의 결과를 낳는다. 어떤 전략, 어떤 코딩을 해야 주어진 시간 자원 속에서 문제를 풀이할 수 있을지 고민한 흔적이라고 볼 수 있겠다.

 

오늘은 골치를 가장 많이 썩였던 min / max 함수에 대해 실험해보고자 한다.

 

---

1. Min vs If, 최솟값 탐색

전체 중 최솟값 혹은 최댓값을 구할 때가 종종 있다. 파이썬의 경우 min, max 함수를 통해 이를 지원하지만, if문을 통해 갱신하는 경우도 존재한다. 둘 중 어떤 경우가 더 시간적으로 좋은 결과를 낼지 테스트해보자. 총 100000개의 원소를 지닌 리스트의 최솟값을 찾는 task를 100번 수행 후 소요 시간에 평균을 내볼 것이다.

 

가설 : If문이 빠를 것이다. min 역시 함수 호출이므로 호출에 소요되는 시간이 매우 많이 소모된다.

 

테스트 코드 1. Average case

 

from time import perf_counter
import random

time_result1, time_result2 = 0., 0.

for i in range(100) :
  lst = random.sample(range(100000), 100000)
  result1, result2 = 100001, 100001
  
  for num in lst :
    start = perf_counter()
    result1 = min(result1, num)
    time_result1 += perf_counter() - start
  
  for num in lst :
    start = perf_counter()
    if result2 > num :
      result2 = num
    time_result2 += perf_counter() - start

print('result1 : {}, time : {}'.format(result1, time_result1 / 100))
print('result2 : {}, time : {}'.format(result2, time_result2 / 100))

 

결과 : 

result1 : 0, time : 0.10285725604333493
result2 : 0, time : 0.03583028853248834

 

 

테스트 코드 2. Best Case

 

from time import perf_counter
import random

time_result1, time_result2 = 0., 0.

for i in range(100) :
  lst = list(range(100000))
  result1, result2 = 100001, 100001
  
  for num in lst :
    start = perf_counter()
    result1 = min(result1, num)
    time_result1 += perf_counter() - start
  
  for num in lst :
    start = perf_counter()
    if result2 > num :
      result2 = num
    time_result2 += perf_counter() - start

print('result1 : {}, time : {}'.format(result1, time_result1 / 100))
print('result2 : {}, time : {}'.format(result2, time_result2 / 100))

 

결과 :

result1 : 0, time : 0.11053413013209137
result2 : 0, time : 0.03933680136246039

 

 

테스트 코드 3. Worst Case

 

from time import perf_counter
import random

time_result1, time_result2 = 0., 0.

for i in range(100) :
  lst = list(range(100000-1, -1, -1))
  result1, result2 = 100001, 100001
  
  for num in lst :
    start = perf_counter()
    result1 = min(result1, num)
    time_result1 += perf_counter() - start
  
  for num in lst :
    start = perf_counter()
    if result2 > num :
      result2 = num
    time_result2 += perf_counter() - start

print('result1 : {}, time : {}'.format(result1, time_result1 / 100))
print('result2 : {}, time : {}'.format(result2, time_result2 / 100))

 

결과 :

result1 : 0, time : 0.10811568740195071
result2 : 0, time : 0.05120373930654751

 

테스트 결과, 다음과 같은 두 가지 현상을 발견할 수 있다.

• 모든 경우에 대해 min 함수를 사용하는 것보다 반복문을 사용하는 것이 훨씬 더 나은 결과를 가져온다.
• 또한 조건문 및 함수 호출의 양 쪽 모두  Worst, Average, Best 간 상관관계가 보이지 않는다. 원래 예상했던 바로는 Worst > average, Best순으로 시간이 소요되리라 예측했다. 조건문 만족시 값을 대입하므로, 조건문 만족 여부에 따라 실행되는 연산량이 차이가 있을 것이라 예측했기 때문이다. min 함수의 경우 대소비교의 결과값을 항상 대입하므로 오차 범위 내에 존재하지만, IF 조건문의 경우 그러한 차이를 발견할 수 없었다. (이유를 아시는 분은 제보 바랍니다...!)

 

번외 : 리스트 전체 min

 

 

from time import perf_counter
import random

time_result1, time_result2, time_result3 = 0., 0., 0.
result1, result2, result3 = 100001, 100001, 100001
for i in range(100) :
  ### average
  lst = random.sample(range(100000), 100000)
  start = perf_counter()
  result1 = min(lst)
  time_result1 += perf_counter() - start
  
  ### best
  lst = list(range(100000))
  start = perf_counter()
  result2 = min(lst)
  time_result2 += perf_counter() - start

  ### worst
  lst = list(range(100000-1, -1, -1))
  start = perf_counter()
  result3 = min(lst)
  time_result3 += perf_counter() - start
  


print('result1 : {}, time : {}'.format(result1, time_result1 / 100))
print('result2 : {}, time : {}'.format(result2, time_result2 / 100))
print('result3 : {}, time : {}'.format(result3, time_result3 / 100))​

result1 : 0, time : 0.01709344326012797
result2 : 0, time : 0.00829065128989896
result3 : 0, time : 0.007252838139902451

 

그렇다면 리스트 전체를 한 번에 min 함수의 입력으로 넣는다면 어떻게 될까? 놀랍게도(어쩌면 놀랍지 않게도), 원소 하나하나를 비교하는 경우 모두보다(조건문과 min 모두보다) 훨씬 더 나은 성능을 보여준다! 단 한번의 함수 호출만이 이루어지므로 오버헤드가 극명하게 줄기 때문이다. 또한 재밌는 점은, 이 경우에는 average보다 best, worst 양 쪽에서 더 높은 성능을 보여준다(내부 구조가 궁금해지는 순간이다. 아마 가설을 세워보자면, 리스트 정렬 -> 특정 위치의 원소 반환 알고리즘의 경우 다음과 같은 현사을 보여줄것이라 생각한다. 아시는 분은 제보바람!)

 

---

요약

• 고정되지 않은(즉 실시간으로 값이 업데이트되거나 총 값의 크기를 모를 경우) 경우의 최소/최대를 구할 경우 조건문을 사용하는 것이 시간상 더 효율적이다.
• 고정된 길이의 값 중에서 최소/최대를 구할 때는 min/max 함수 호출이 더 효율적이다(다만 값의 길이가 짧은 경우는 조건문이 더 효율적일지도 모른다)