본문 바로가기

Python

Python 기본함수들 성능속도 비교

Python 3.5 기준입니다


Input() VS sys.stdin.readline

입력을 10번정도는 크게 차이가없다.. 하지만 수만번이상의 입력을 요하는 작업이면  sys.stdin.readline 이  눈에띄게 차이날정도로 빠르다


자료구조선택문제


python은 배열이없다. 배열역할을 대신해주는 built-in 자료구조로 list, set, dict, tuple 가 있습니다.

이들을 어떻게 사용할지는 각각 특징이 있으므로 상황에 맞게끔 사용하면 됩니다.

예를들면

중복을 허용하지않는 구조일경우 set을 또한 데이터의 자료순서(혹은 정렬된상태)가 따로필요하지않다면 
set을 사용하시는게 속도적인 측면에서 큰 이점을 얻을수 있습니다.

표로 정리해드리자면

list 

tuple

set 

dict 

 데이터수정, 순서가 필요한경우

데이터의 읽기만 필요한경우 

중복된값을 불허하는경우

상황것..

 

 

순서가 불필요한 경우 

 

 

 

 

 


특히 set의 이점에 대해 알려드리자면 예를들어 x가 배열 arr에 포함됬는지 확인하려면 보통 x in arr 을 사용합니다

리스트 구조는 이것을 구하는데 평균적으로 O(n)의 시간이 들지만 set은 O(1)의 시간으로 자료구조가 클수록 엄청난 시간적 이점이있습니다.


또한 list의 대체형으로 deque라는 컬렉션 클래스가 있습니다 이건  stl처럼 import해서 사용하시면 되는데

list의 경우 pop(0)의 경우 O(n)의 시간을 소비합니다. 하지만 deque는 양쪽으로 열린구조??로 popleft를 지원하고 pop, popleft

append, appendleft 모두 O(1)의 시간을 소비하는 알아두시면 아주좋은 자료구조입니다.


이것이 얼마나 큰이점인지는 다음 스크린샷을 보시면 알수 있습니다. 


EX) 입력을 수십만번, list의 pop(0)을 수백번써야되는 알고리즘에서 sys.stdin.readline, deque로 변형시 걸리는 시간 차이


(시간측정은 알고리즘문제사이트 baekjoon에서 측정하였습니다.)


python이 확실히 인터프리터언어고 c같은 언어 심지어 java보다 느린언어지만 

list set tuple deque같은 엄청난 편의성을 가진 문법적구조로 다른언어에서 2,3천줄이상쓸것을 1천줄로 줄여주는 정말 편리한 언어인것같습니다.

'Python' 카테고리의 다른 글

Python 실행파일(exe)로 배포하기  (2) 2016.11.08
Python 기초정리  (0) 2016.11.02