Programming Pearls/Column1

파일 내용의 소트를 어떻게 할 것인가?

대부분의 언어에는 소트가 이미 구현되어 있다. 그런데 꼭 새로운 나만의 소트를 만들어야 될때가 있다. 레코드가 한 천만개쯤 된다고 하자.이것을 우리가 알고 있는 버블소트, 퀵소트 같은 것으로 하기에는 메모리가 많이 든다. 32bit(4byte)의 정수라고 한다면, 40메가바이트가 필요하다. 하지만 어떤 작업을 할때에, 우리가 소트에 할당할 수 있는 공간은 1메가 남짓이라고 가정하자. 시간이 많이 걸려서도 안된다. 어떻게 해야 할 것인가? 이 레코드들은 7자리 전화번호이기 때문에 같은 것이 없다고 한다.

• 입력 : 많아 봐야 n개의 정수. 각각의 n은 천만보다 작다. 똑같은 숫자가 두번이상 나오면 안된다. 그 숫자랑 관련된 데이터가 없다.
  
• 출력 : 오름차순으로 정렬된 숫자들
  
• 제한 : 메모리를 1메가 정도밖에 사용할 수 없음. 디스크 공간 넉넉함. 수행시간이 수분을 넘으면 안됨. 10초 정도면 괜찮음.
  
  

첨에는 머지 소트를 했었는데 버렸다. 다른 방법으로는, 각각의 숫자를 4byte로 표현하면 현재 메모리에 250,000개를 담을 수 있다. 250000개를 소트하고, 또 250,000개 읽고... 이걸 40번 하는 거다. 머지 소트는 중간 작업 파일에의 엑세스가 자주 일어나고, 두번째 방법은 입력을 40번을 받아야 한다는게 문제다. 이것 두가지의 장점을 잘 조합해서 입력은 한번, 중간 작업 파일이 없게는 할 수 없을까?

비트맵, 혹은 비트 벡터라 불리우는 방법이 유용할듯 싶다. 예를 들어 맥시멈 10미만의 숫자라 할때에, {1,2,3,5,8}을 표현해 보면, (0 1 1 1 0 1 0 0 1 1)이 된다. 있으면 1, 없으면 0인 것이다. 한 숫자당 1비트만 할당을 해서, 그것의 인덱스로 처리를 하는 것이다. 앞에서도 말했듯이, 미니멈과 맥시멈의 너비가 작고, 같은 숫자가 없으며, 관련된 데이터가 없다는 측면에서 이 방법을 쓸 수 있는 것이다. 대강의 코드는 다음과 같다.

~cpp 
# 배열값 0으로 셋팅
for b in bits:
	b=0
# 있으면 1
for e in inputFile:
	bits[e]=1
# 1인것만 출력
for b in bits:
	if b==1:
		print b

이것의 수행시간은 Θ(n)이다. 이 챕터는 문제를 주의 깊게 분석하다 보면, 가끔 엄청난 이득을 가져다 줄때가 있다는 교훈을 주고 있다. 문제 정의는 문제 풀이의 90프로다. 일반적으로 많은 공간을 사용하면 적은 시간이 소요된다고 한다. 그런데 비트맵 소트는 시간도 줄고, 공간도 줄어들었따. 적은 데이터를 다루는 것은, 그것을 수행하는 데에 더 적은 시간이 든다는 것이다. 그리고 데이터를 디스크에 두기 보다는 메모리 상에 두는 것이 디스크 액세스 같은 시간 걸리는 일을 줄일 수가 있는 것이다. 프로그램을 간단하게 짜자. 유지보수도 쉽고, 견고할 것이다.

ProgrammingPearls