•
한 프로그래머가 내게 질문을 했다고 생각해보자. 디스크 파일을 어떻게 정렬하지?
1. 대화
•
저자의 실수는 단순히, 질문에 대한 답을 하려 했던 것이었다. 저자는 그에게 디스크 상에서 병합 정렬을 어떻게 구현하는지 간단히 설명해주었다.
◦
이는 문제를 해결하고자 했던 그에게 적절한 답이 아니었다.
•
질문을 해결하려 하지말고 대화를 통해 맥락을 제공받자. 맥락을 알게 되면 문제가 더욱 명확해진다. 요구사항을 정확히 파악할 수 있고 우리는 더 다양한 접근법을 생각해볼 수 있게 된다.
•
그의 요구사항은 정확히 이러이러했다.
◦
먼저 해당 프로세스를 위해 1MB 정도의 메모리 용량을 할당받을 수 있었다.
◦
데이터는 최대 1천만 개고 정렬의 대상이 되는 데이터들은 중복이 존재하지 않는 7자리 양의 정수다.
◦
원하는 출력은 오름차순으로 정렬된 숫자의 파일이었다. 또한 성능에 대한 요구사항도 있었다.
◦
사용자는 대략 한 시간에 한 번 정도 정렬된 파일을 요청하는데, 이때 정렬이 완료될때까지는 아무 작업도 할 수 없었으므로 대략 10초의 시간 안에 끝나야하며 적어도 2분 안에는 완료되어야 했다.
2. 정확한 문제 기술
•
위의 요구사항을 토대로 우리가 잘 알고 있는 입력, 출력, 제약조건의 형태로 문제를 기술해보자.
•
입력
◦
최대 n의 양의 정수를 포함하는 파일로, 각 숫자는 n보다 작고, 이다.
◦
어떤 숫자가 두 번 이상 나오는 것은 치명적인 에러이며 정수 이외에 관련된 데이터는 없다.
•
출력
◦
입력된 정수를 오름차순으로 정렬한 리스트를 반환한다.
•
제약조건
◦
메모리를 대략 1MB 정도 사용할 수 있으며 디스크 공간은 충분하다.
◦
실행시간은 최대 2분 정도며 10초 정도 안에 작업을 끝낼 수 있으면 충분하다.
•
명확해진 명세 사항을 기반으로 우리는 앞서 질문과 비교했을 때 그 프로그래머에게 어떤 조언을 해줄 수 있게 되었을까?
3. 프로그램 디자인
•
가장 먼저 떠오르는 방법은 일반적인 디스크 기반의 병합 정렬을 사용하는 것으로 정수를 정렬한다는 사실을 반영하여 프로그램을 조금 다듬으면 문제를 해결하는데 도움이 될 것이다.
◦
병합 정렬 프로그램은 입력 파일을 한 번에 읽어 작업 파일을 여러번 읽고 쓰는 과정을 통해 정렬을 하고 결과를 한 번에 저장한다.
•
두 번째 방법은 이 정렬 문제의 특별한 성질을 더 많이 사용하도록 최적화를 수행하는 것이다.
◦
만약 각 숫자를 7바이트에 저장한다면 사용 가능한 메모리(약 1MB)에 대략 14만 개의 숫자를 저장할 수 있다. 그러나 각 숫자를 32비트 정수로 표현한다면 대략 25만 개의 숫자를 저장할 수 있다.
▪
따라서 우리는 최대 1000만 개의 데이터를 40번 정도만 읽는 프로그램을 사용하게 될 것이다.
▪
각 패스에서 25만 개의 숫자를 메모리로 읽어들여 정렬한 다음 파일에 저장하는 작업을 40번 반복한다.
◦
40-패스 알고리즘은 입력 파일을 여러 번 읽지만 출력은 단 한번만 저장하며 중간 파일도 생기지 않는다.
•
우리는 두 방법의 장점을 각각 조합하여 입력 파일을 한 번만 읽게하고 중간 파일이 생기지 않게끔 만들어볼 수 있다.
◦
먼저 이는 입력 파일의 1000만 개의 데이터를 1MB 데이터로 표현해야 가능하다.
4. 구현 스케치
•
이런 관점에서 봤을 때, 메모리를 효율적으로 사용할 수 있는 비트맵 또는 비트 벡터 표현법을 사용해볼 수 있다.
•
파일 내의 정수 집합을 표현하기 위한 비트맵 자료 구조가 주어졌다 했을때, 프로그램은 자연스럽게 세 단계로 작성될 수 있다.
◦
첫 번째 단계에서는 모든 비트를 0으로 초기화한다.
◦
두 번째 단계에서는 파일로부터 각각의 정수를 읽어 해당 비트를 1로 설정한다.
◦
세 번째 단계에서는 각각의 비트를 확인하고 비트가 1로 되어있는 경우 그에 해당하는 숫자를 기록하여 정렬된 출력 파일을 생성한다.
•
그 프로그래머가 문제를 해결하는 것은 이정도로 충분할 것이다.
5. 원리
•
이는 효율적인 생산성을 이끌어내었다. 기존의 오래걸리던 작업을 몇 시간만에 처리해주었고 그리 어려운 구현도 아니었다.
•
이는 다음과 같은 교훈으로 연결되는 데 다음과 같다. 작은 문제에 대한 주의 깊은 분석으로 때로는 엄청난 실질적 이익을 얻을 수 있다.
◦
이 경우, 몇분 동안의 주의 깊은 연구로 코드 길이, 생산성, 실행시간을 10배 이상 줄인 케이스였다.
◦
그러나 이처럼 특정한 데이터에 종속적인 구조는 특정 부분의 명세가 변경되는 경우 수정이 불가피할 것이다.
•
이 장에서 배운 일반적인 원리는 다음과 같다.
◦
정확한 문제 정의
▪
문제를 정의하는 것은 그 문제를 해결함에 있어서 큰 몫을 차지한다.
◦
비트맵 데이터 구조
▪
이 데이터 구조는 원소가 중복되지 않고 원소와 관련된 다른 데이터도 없는 촘촘한 유한 집합을 표현한다.
◦
다중 패스 알고리즘
▪
이 알고리즘은 입력 파일을 여러번 읽어 각 단계마다 조금씩 작업한다.
◦
시간-공간 상충관계인 것과 아닌 것
▪
일반적으로 프로그래밍 분야에는 시간-공간 상충관계가 많다. 시간을 더 들이면 공간을 덜 사용할 수 있다는 것이다.
◦
단순한 디자인
▪
추가할 것이 더 이상 없을 때가 아니라. 제거할 것이 없을 때 디자이너는 완벽함에 도달했다는 것을 알게 된다고 프랑스의 항공기 디자이너인 Antoine de Saint-Exupery가 말했다.
▪
더 많은 프로그래머가 자신의 작업을 평가함에 있어 이 말을 기준으로 삼아야 한다. 보통 간단한 프로그램이 복잡한 프로그램보다 더 신뢰하기 쉽고 안전하며 견고하고 효율적일 뿐만 아니라 유지보수마저 쉽다.
