[BOJ] 10989번: 수 정렬하기 3 / Python - 성능과 메모리 사용 간 최적화

https://www.acmicpc.net/problem/10989

 

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램을 작성해야 한다.

(조건: 1 ≤ N ≤ 10,000,000 이며,  각 숫자는 10,000보다 작거나 같은 자연수)

메모리 제한이 단 8MB에 불과해, 메모리 최적화가 중요한 문제이다.

 

단순히 list를 정렬하는 방식으로는 해결할 수 없다.

숫자의 갯수가 1천만개까지 가능하기 때문에, 이를 모두 담기 위한 list의 메모리 크기를 대략 계산해보자.

• 10,000 이하의 자연수가 각각 int로 저장되는데, 파이썬의 int 형은 64bit 시스템에서 28 byte 정도가 소요된다고 한다.
• List 자체는 각 자연수에 대한 포인터를 저장하는데, 그리고 각 포인터는 8 byte를 차지한다.

결론적으로, 단순히 모든 숫자를 list에 개별 저장하려면, 대략 (8 byte + 28 byte) * 10,000,000 = 360MB의 메모리가 필요하므로, 문제의 제한 사항을 아득히 뛰어넘게 된다.

 

대신 Counting Sort(계수 정렬)을 사용해야 한다. 

Counting Sort는 주어진 데이터에서 각 값의 빈도를 세어 해당 값들이 몇 번 나타나는지 기록한 후, 빈도 정보에 따라 데이터를 정렬하는 알고리즘이다. 이 알고리즘은 데이터의 값의 범위가 적고, 빈도가 많은 경우에 매우 효율적이다. 시간 복잡도는 O(N + K)로, N은 데이터의 개수, K는 데이터의 값 범위이다. 다만, 값의 범위가 너무 넓으면 메모리 사용량이 급격히 증가할 수 있다

 

Couting Sort를 사용해 간단히 구현해봤다. 작은 숫자부터 시작해서, 각 숫자의 발생 갯수만큼 출력하면된다.

그러나 아래처럼 메모리 초과가 발생하게 되었다.

메모리 초과 발생 코드

import sys

n = int(next(sys.stdin))
l = [0] * 10_001
for i in sys.stdin:
    l[int(i)] += 1

for i in range(1, 10_001):
    sys.stdout.write(f"{i}\n" * l[i]) # 메모리 초과 원인

메모리 초과가 발생한 이유는, 최종 결과 출력시 문자열 곱셈을 너무 naive하게 수행했기 때문이다. l[i]의 값이 최대 10,000,000이 될 수 있기 때문에, 수천만 byte짜리 string이 생길 수도 있는 코드 작성이다.

 

위 오류를 수정해서 통과하는 코드를 작성했다.

정답 코드 -  메모리 사용 

import sys

n = int(next(sys.stdin))
l = [0] * 10_001
for i in sys.stdin:
    l[int(i)] += 1

for i in range(1, 10_001):
    for _ in range(l[i]):
        sys.stdout.write(f"{i}\n")

개별 숫자에 대해 sys.stdout.write()를 일일이 호출하는 방식이다. 이 방식은 여러 문자를 합친 문자열을 출력하지 않으므로, 메모리 공간은 그만큼 사용하지 않을 수는 있으나, sys.stdout.write() 의 호출이 그만큼 증가하므로 성능에 페널티가 있을 수 있다.

 

이어서, 개별 숫자에 대해 일일이 sys.stdout.write() 를 호출하지 않고, 그룹화시킨 것에 대해 호출하는 최적화를 시도했다.

성능 개선된 정답 코드 -  write 함수 호출 횟수 줄이기(성능과 메모리 사용 간의 최적화)

import sys

n = int(next(sys.stdin))
l = [0] * 10_001
for i in sys.stdin:
    l[int(i)] += 1

BUFFER_SIZE = 1_000
for i in range(1, 10_001):
    for _ in range(l[i] // BUFFER_SIZE):
        sys.stdout.write(f"{i}\n" * BUFFER_SIZE)
    for _ in range(l[i] % BUFFER_SIZE):
        sys.stdout.write(f"{i}\n")

개별 숫자를 1,000개씩 buffer에 모아서 출력하도록 변경했다.

개별 숫자의 문자열("1"~"10000")의 크기는 5 byte이내이므로, 각 buffer의 메모리 크기는 5,000 byte에 해당된다.

이러면 8 MB의 메모리 제약 조건을 안전하게 지키면서, sys.stdout.write()의 호출 횟수를 크게 줄일 수 있다.

예를 들어, 숫자 1이 1,000번 등장했다고 가정하자.

이전 코드에서는 1에 대해  sys.stdout.write("1\n") 를 1,000번 호출했어야 했으나, 개선된 코드에서는 sys.stdout.write("1\n" * 1000) 를 한번만 호출하면 된다.

 

 

추가 개선 방법?

• input, output 함수를 다른 것을 사용해서 입출력에서 성능 개선을 볼 수 있을 것 같다.
• 그렇지만 현재 작성된 코드가 간결하기 때문에 불필요할 수도 있다.