백준 2751번
nlogn의 성능으로 수 정렬하기
풀이 1. 힙정렬(우선순위큐)
결과는 통과! 하지만 2292ms로 생각보다 속도가 안나왔습니다.. 다른 성능좋은 제출들을 살펴보니 PyPy3로 선택을 했더라구요.. 그래서 언어를 PyPy3로 똑같은 코드를 돌려보니 1428ms로 거의 절반정도 줄었습니다🤗
import sys
import heapq
N = int(sys.stdin.readline())
pq = []
for _ in range(N):
heapq.heappush(pq, int(sys.stdin.readline()))
for _ in range(len(pq)):
print(heapq.heappop(pq))PyPy와 Python3의 차이
- Python3의 동작방식 : 작성한 소스코드 -> C언어로 컴파일후 실행
- PyPy의 동작방식 : JIT컴파일도입 , 프로그램을 실행하는 시점에서 필요한 부분 컴파일해서 실행 또한 자주쓰이는 코드들을 캐싱 -> 인터프리터의 느린속도를 개선가능
결론, 간단한 코드에서는 Python3가 메모리와 시간쪽에서 둘다 유리할 수 있지만 반복이 많은 복잡한 코드에서는 PyPy가 캐싱을 하기때문에 실행속도를 개선할 수 있습니다.
풀이 2. sort함수 + 입출력교체
-
시간이 빨랐던 코드들의 또 다른 특징들은 입출력을 sys라이브러리를 이용한다는 것입니다. 위 코드에서 입출력방식을 바꾸고 sort함수로 정렬을 진행했습니다.
-
결과는 580ms!! 엄청나게 빨라졌네요 앞으로 입출력은 sys라이브러리로 해야겠습니다. 한가지 특징은 sys.stdout.write가 str형태만 인자로 받는다는 것과 print()와는 다르게 끝에 개행없이 출력됩니다
import sys
N = int(sys.stdin.readline())
nums = []
for _ in range(N):
nums.append(int(sys.stdin.readline()))
nums.sort()
sys.stdout.write('\n'.join(map(str,nums)))sys.stdin, sys.stdout vs input(), print()
먼저 sys.stdout.write()와 print()는 속도에 큰 차이를 주지 않습니다. 문제는 입력에 있습니다. 간단한 코드로 두 함수의 차이를 알아보겠습니다!
<예제코드>
import sys
N = sys.stdin.readline()
M = input()
print(N)
print(M)
<출력결과>
-
sys.stdin.readline() : 입력받은 것을 개행까지 모두 출력합니다
-
input(prompt) : 이 함수는 prompt문자열을 인자로 받습니다. 물론 아무것도 안넘겨줘도 되지만 입력을 받기전 prompt를 출력해줘야합니다. 또한 456+엔터를 입력하면 출력은 456이 됩니다. 즉 엔터(개행)은 입력에 들어가지 않은것인데요. 그 이유는 바로 input이 입력을 받고 strip()을 실행해서 개행을 제거합니다. 이 두가지 이유로 readline보다 시간이 오래걸리며 입력값이 많아질수록 그 차이는 커집니다.
