제시된 문제는 다음과 같다.
n(최대 10,000,000 개 이하)개의 0보다 큰 정수로 이루어진 파일이 있다. 동일한 값은 존재하지 않으며, 정수 이외의 데이터는 없다.
이 파일에 있는 정수들을 어떻게 정렬할 수 있을까?
이 파일에 있는 정수들을 어떻게 정렬할 수 있을까?
- 메모리는 최대 1 MB까지만 사용할 수 있다.
- 하드 디스크는 충분히 사용할 수 있다.
- 몇 분안에 실행이 완료되어야 한다.
디스크를 이용한 Merge Sort
Merge Sort는 다음을 참고한다. 이 문제를 해결하는데 적합한 알고리즘은 아니다.
Multipass Sort
정수를 7 바이트로 표시하면 1 MB 메모리에 약 143,000 개의 정수를 올려 놓을 수 있다.
1024 * 1024 / 7 = 약 149,796
정수를 32 비트로 표시하면 1 MB 메모리에 약 250,000 개의 정수를 올려 놓을 수 있다.
1024 * 1024 / (32 / 8) = 약 262,144
이 정보를 기초로 파일을 여러번 읽어 문제를 해결할 수 있다.
첫번째 읽을 때는 0에서 249,999 사이 정수만을 메모리에 올려 놓은 후에 정렬을 하여 결과를 파일에 쓴다. 이렇게 반복적으로 마지막에는 9,750,000에서 9,999,999 사이 정수만을 대상으로 이 작업을 수행한다.
반복적으로 40 차례 파일을 일으면 모든 정수를 정렬할 수 있다.
10,000,000 / 250,000 = 40
비트맵을 이용한 처리
정수 이외의 데이터는 없고, 중복된 값이 없다는 전제 조건을 이용하면 간단하게 비트맵으로 문제를 해결할 수 있다.
즉, 크기가 10,000,000인 비트 배열을 만들어서 특정 정수가 존재하면 다음과 같이 처리한다. 예를 들어, 13,223가 존재하면 다음과 같이 한다.
bit[13223] = 1;
* 1 MB 이상 메모리가 필요하다. 1 MB가 엄격한 제한 조건이라면 Twopass Sort와 함께 사용한다.
가상 코드는 다음과 같다.
/* phase 1: initialize set to empty */
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file
비트맵을 이용한 해결 방법은 범용적이지는 않다. 즉 특정 문제를 해결하는데 적합하다. 그런데 특정 문제를 해결하는데는 탁월한 방법이다.
문제를 해결하는데 가장 중요한 것은 문제를 이해하고 정의하는 것이다.
Careful analysis of a small problem can sometimes yield tremendous practical benefits.
No comments:
Post a Comment