sort(), sorted() 실행 시간 in 백준

개요

파이썬 코테 스터디를 진행하던 도중 팀원의 sort(),sorted()에 대해 시간복잡도 차이가 난다고 했어요.

 

Timsort()를 이용해서 n log (n)의 안정된 시간 복잡도를 둘 다 사용하는데 왜 백준에서 실행을 했을 때

 

Timsort 알아보기 : https://d2.naver.com/helloworld/0315536

 

sort()만 정답처리가 됐는지 궁금해서 실험을 해봤습니다.

실험 결과

import time
import statistics
import random
import string
# 10회 비교
sorted_value = []
sort_value = []

for _ in range (10):
# 더미 데이터 생성
  dummy_input_a = [f'{random.choice(string.ascii_lowercase)}{random.randint(1, 26)}person_' for _ in range(100)]
  dummy_input_b = [f'{random.choice(string.ascii_lowercase)}{random.randint(1, 26)}person_' for _ in range(100)]


# 더미 데이터 사용
  N, M = len(dummy_input_a), len(dummy_input_b)
  a = set(dummy_input_a)
  b = set(dummy_input_b)

  sorted_start_time = time.time()
  sorted_c = sorted(list(a & b))
  sorted_end_time = time.time()
  sorted_value.append(sorted_end_time - sorted_start_time)

  sort_start_time = time.time()
  c=list(a & b)
  c.sort()
  sort_end_time =time.time()
  sort_value.append(sort_end_time - sort_start_time)

for i in range(10):
  print("sorted : {:.15f}".format(sorted_value[i]),end = " ")
  print("sort : {:.15f}".format(sort_value[i]))

  if sorted_value[i] > sort_value[i]:
        print("{:.2f} 배 \tsort_value 빠름".format(sorted_value[i] / sort_value[i]))
  else:
        print("{:.2f} 배 \tsorted_value 빠름".format(sort_value[i] / sorted_value[i]))
print('--------------------------------------------')
print("sorted avg : \t{:.15f}".format(statistics.mean(sort_value)))
print("sort avg : \t{:.15f}".format(statistics.mean(sorted_value)))

 

sort()함수가 1.5배정도 보통 빠른걸 볼 수 있었어요

---------------------------------------------------------------------

sorted :  0.000015020370483 sort :  0.000007152557373 2.10 배  sort_value 빠름

sorted :  0.000010728836060 sort :  0.000006675720215 1.61 배  sort_value 빠름

sorted :  0.000009775161743 sort :  0.000005006790161 1.95 배  sort_value 빠름

sorted :  0.000010013580322 sort :  0.000006198883057 1.62 배  sort_value 빠름

sorted :  0.000009775161743 sort :  0.000006198883057 1.58 배  sort_value 빠름

sorted :  0.000011444091797 sort :  0.000007152557373 1.60 배  sort_value 빠름

sorted :  0.000012874603271 sort :  0.000008583068848 1.50 배  sort_value 빠름

sorted :  0.000010967254639 sort :  0.000006914138794 1.59 배  sort_value 빠름

sorted :  0.000011205673218 sort :  0.000007629394531 1.47 배  sort_value 빠름

sorted :  0.000011205673218 sort :  0.000007390975952 1.52 배  sort_value 빠름

---------------------------------------------------------------------

정렬 속도 비교된 사이트

https://www.acmicpc.net/blog/view/58

여기서도 일반적으로 sort()가 sorted()보다 빠르다는 것을 알 수 있었어요

PyPy3 sort() < PyPy3 sorted() < python 3 sort() < python 3 sorted() 

순서로 빠르기가 나온다고 하네요

같은 코드 다른 결과

 

같은 코드를 제출해도 백준 서버 상황에 따라 시간 초과가 날 수도 안날 수도 있다고 합니다

위에 보면 맨 아래 코드랑 맨위 1,2번은 같은 코드에요 같은 코드여도 실행 속도에는 차이가 있어요

그런데 시간제한이 2초인데 왜 ? 4초 가까이인데 통과일까요?

백준의 보너스 시간

C언어랑 Python이랑 같은 시간 제한을 두면 python은 거의 통과를 못할거에요

그래서 보너스 시간이라는 개념이 존재한다고 해요

https://help.acmicpc.net/language/info 

Python, PyPy3은 시간제한이 3배+2초 -> 2초면 8초까지 보너스 시간제한

 

일반적으로 sort()가 더 빠르다는 사실은 알게됐네요 :)