[백준 10989번] Counting sort, 메모리 초과, PyPy3 와 Python3 / 22.10.31

이 문서는 전문적이지 않습니다.

 

 

입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

해당 문제는 제한 중 "8 MB" 메모리 제한이 있다.

 

 

#1

 

 

첫 시도, 빠르게 정렬하는 도수 정렬을 통해 문제를 해결하고자 했다.

 

도수 정렬을 위해서는 다음과 같은 알고리즘을 통해 만들어준다.

 

1. 도수 분포표 만들기

2. 누적 도수 분포표 만들기

3. 작업용 배열 만들기

4. 배열 복사하기

 

import sys

n = int(sys.stdin.readline())

listQ = []
for i in range(n):
    listQ.append(int(sys.stdin.readline()))

# 리스트 최대 
maxQ = 10000

# 도수분포 생성
f = [0] * (maxQ+1)

for i in listQ:
    f[i] += 1

# 누적 도수분포
for i in range(1,len(f)):
    f[i] += f[i-1]


resQ = [0] * (n+1)

for i in range(1,n+1):

    resQ[f[listQ[-i]]] = listQ[-i]
    f[listQ[-i]] -= 1

for i in resQ[1:]:
	print(i)

 

정렬은 sort() 만 쓰면 다 되는줄 알았는데 ...

 

#2

 

 

두번째 시도, 메모리의 할당에 대한 이해.

메모리가 어느 순간 누적되는가에 대해 알게된 것은

변수 생성 과 데이터 할당하는 시점이었다.

그리고 가장 중요한 부분은

for 문에서 데이터를 재할당 하는 경우였다.

listQ에 input 값을 append 시키는 시점이 메모리 재할당시점이었다.

https://wikidocs.net/21057 참고

 

변수들을 쳐내고 for 문을 줄이고 코드를 많이 줄이다 보니 코드길이가 절반 이하가 됐다.

물론, 너무 막막하여 구글의 답글도 참고하여 counting sort 에 대해 많은 학습을 할 수 있었다.

 

import sys
n = int(sys.stdin.readline())
f = [0] * 10001
for i in range(n):
    f[int(sys.stdin.readline())] += 1
for i in range(10001):
    if f[i] != 0:
        for j in range(f[i]):
            print(i)

문제의 조건중 자연수 10000 이하 라는 힌트를 활용해 미리 범위를 선언하며, 기존의 append 구문을 삭제했다.

input과 동시에 누적 도수분포표를 작성하게 만듦으로써 listQ 를 아예 할당하지 않을 수 있었다.

 

 

 

 

 

 

하지만 역시나 내 마음처럼 해결되지 않았다..

 

 

 

 

 

 

거짓말 같이 메모리 초과가 떴다.

 

 

 

#3

 

 

세번째 시도, 무언가 잘못됐음을 느꼈다.

 

무조건 PyPy3 을 사용하면 되겠지,

 

 

불현듯 내가 지난날 했던 생각이 떠올랐다.

언어는 PyPy3 을 사용하면 된다.

input 대신 sys.stdin.readline() 을 사용하면 된다.

 

PyPy3 가 그러면 뭔지, 설마 PyPy3 때문인지 알아볼 차례다.

 

PyPy3에서는 실행시 자주 쓰이는 코드를 캐싱하는 기능이 있다.
즉  메모리에 저장하고 있기 때문에 실행속도를 개선할 수 있다는 것이다.

출처: https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

Python3 와 PyPy3 차이

 

위 블로그에서 알게된 점은, PyPy3 가 캐싱하고 있는 코드로 인해서 속도가 빨라지지만, 낮은 용량의 코드에서는 기존 Python3 보다 더 많은 메모리를 필요로 할 수 있다는 점이다.

스택 오버플로우 에서도 이런 이슈를 확인할 수 있었다. 한번 확인해보는 것을 추천한다.

https://stackoverflow.com/questions/45117672/pypy-large-memory-usage-compared-to-cpython

PyPy large memory usage compared to CPython

 

추가적으로 좋은 게시글을 하나 더 공유한다. 시간에 여유가 있다면, 한번 훑어봐도 재미있는 것 같다.

PyPy3의 속도가 빠름에도 어째서 CPython을 사용하는지에 대한 이야기이다.

https://stackoverflow.com/questions/18946662/why-shouldnt-i-use-pypy-over-cpython-if-pypy-is-6-3-times-faster

Why shouldn't I use PyPy over CPython if PyPy is 6.3 times faster?

 

 

 

 

 

#4

 

 

해결됐다. 정답은 아니어도 많은 것을 알게됐다.

 

 

 

분명 이러한 방법이 유일한 해결방법은 아닐 것이다.

하지만 정글에 정답은 없기 때문에 초록색 글씨에 만족하기로 했다.

 

 

 

 

 

 

긴 글 읽어주셔서 감사드립니다.

22.10.31