한빛출판네트워크

제공 : 한빛 네트워크
저자 : George T. Heineman
역자 : 이철
원문 : November Column: Welcome to Algorithms in a Nutshell

개요

이 기사는 O’Reilly에서 2008년 10월에 출간된 ‘Algorithms in a Nutshell’ 책과 관련된 내용으로 매월 발행할 칼럼 시리즈의 첫 번째 기사이다.

본 기사는 위의 책과 관련된 소스 코드인 알고리즘 개발 키트(Algorithm Development Kit, ADK)를 다운로드하고 설치하는 과정을 설명한다. 여러분은 책과 관련된 저장소의 Releases 폴더에서 최신 버전의 ADK를 다운로드 할 수 있을 것이다. ADK의 압축을 풀면 ADK/Deplyment라는 폴더를 생성하며, 이 폴더를 $ADKHOME라 부르기로 한다. ADK를 빌드하기 위해서는 폴더에 있는 README.txt 파일을 참고하도록 하며, 본 칼럼에서 필자는 여러분이 ADK를 여러분의 플랫폼에서 적절히 빌드한 것으로 가정한다.

ADK 차례

코드 저장소는 아래 범위에 해당하는 알고리즘의 모든 구현을 포함하며, 숫자는 책의 해당 챕터를 나타낸다.

4. 정렬 : 삽입 정렬, 퀵 정렬, 중간 정렬, 선택 정렬, 힙 정렬, 계산 정렬, 버켓 정렬
5. 검색 : 순차 검색, 이진 검색, 해쉬 검색, 이진 트리 검색
6. 그래프 알고리즘 : 깊이우선 탐색, 너비우선 탐색, Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘, Prim 알고리즘
7. AI의 경로 탐색 : 깊이우선 탐색, 너비우선 탐색, A* 탐색, Minimax, NegMax, AlphaBeta
8. 네트워크 흐름 알고리즘 : Ford-Fulkerson, Edmonds-Karp
9. 계산 기하 : 최소블록집합 탐색, Line Sweep, 최소 이웃 질의, 범위 질의

본 칼럼에서 필자는 C로 구현된 정렬 알고리즘을 사용하는 방법을 설명한다. 추후 칼럼에서는 나머지 챕터를 다룰 예정이다. 또한 필자는 Java, Scheme, C, C++ 등 다양한 언어로 구현된 소스를 제공한다.

11월 코드 샘플 다운로드하기

여러분은 본 칼럼에서 소개하는 코드 샘플을 이곳에서 다운로드 발을 수 있다. 다음의 예제는 표준 리눅스에서 gcc 4.2로 테스트하였다. 추후 칼럼에서는 Eclipse에서 Java 및 다른 언어를 이용하는 예제를 설명할 예정이다. 다운로드 받은 code.zip의 압축을 풀면 “November_2008”이라는 폴더가 만들어진다. 간단하게 사용하기 위해서 code.zip의 내용을 $ADKHOME 디렉토리에 풀어 “ADK” 및 “November_2008” 디렉토리가 한 디렉토리 내에 있게 한다. 리눅스에서는 아래의 명령어를 사용하면 충분하다.

cd $ADKHOME        
cd ../..
unzip code.zip

code.zip 파일의 압축을 적절한 곳에 풀 수 없으면 November_2008/Makefile을 수정하여 $ADKHOME을 여러분의 파일시스템에 위치하게 할 수 있다. November_2008 디렉토리 안에서 make 명령어를 실행하여 본 칼럼에서 사용되는 실행파일을 만든다. November_2008 디렉토리 내에 본 칼럼에서 실행하는 프로그램이 만든 샘플 벤치마크 데이터가 포함된 NovemberData.xls 엑셀 파일이 있다.

정렬 루틴을 위한 API 인터페이스

아래의 코드는 vals[0] .. vals[numElements-1]에 저장된 데이터를 정렬하는 API를 나타낸다.

/**
* Interface to sort the pointer-based information found 
 * in vals. Each element vals[i] points to an element in 
 * the collection to be sorted.
 * @param vals Array of pointer-based information 
 *              in memory

 * 포인터를 이용하여 vals에 저장된 데이터를 정렬하는 인터페이스.
 * 각각의 항목 vals[i]는 정렬될 원소의 배열을 가르킨다.
 * the collection to be sorted.
 * @param vals : 메모리에 저장된 포인터의 배열
 * @param numElements : vals에 저장된 원소의 개수
 * @param cmp : 두 원소를 비교하는 함수
 */
extern void sortPointers (void **vals, int numElements,
                          int (*cmp) (void *a1,

여러분은 QUICKSORT가 정렬을 위한 가장 빠른 알고리즘이라는 것을 알고 있을지도 모르겠다. Algorithms in a Nutshell 책의 4장에서 필자는 어떠한 상황에서 어떤 알고리즘이 가장 좋은 성능을 보이는지 확인하기 위해서 다양한 알고리즘을 비교한다. QUICKSORT가 비교적 작은 데이터인 12,041 라인, 451 페이지의 H.R. 1424 법안 즉, 2008년 긴급 경제 안정화 법령에 대해서 어떻게 동작하는지 보기로 하자.

기준을 잡기 위해 sort 유틸리티가 파일을 정렬하는데 걸리는 시간을 측정한다. sort는 사용자에게 다양한 방법의 구성요소를 이용하여 정렬할 수 있게 하는 복잡한 프로그램이므로 공정한 비교는 아니다. 어쨌든 결과는 다음과 같다.

time sort BillText.txt > /dev/null
0.064u 0.008s 0:00.06 100.0%    0+0k 0+0io 0pf+0w

대략 6/100초의 실행시간을 갖는다.

이제 본 칼럼에서 사용한 코드를 보자. sample.c는 입력 텍스트 파일(사용자가 커맨드라인의 인자로 전달)의 내용을 로드하여 입력의 각 라인의 스트링을 나타내는 포인터의 배열을 생성한다. 일단 배열을 생성한 다음에 sortPointers 함수를 호출하며, 모든 값들이 strcmp에 따라 정렬되어 stdout으로 출력된다. 이 드라이버를 사용하여 몇 가지 실행파일을 생성하며, 이를 평가한다. November_2008 디렉토리에 있는 Makefile은 각 실행파일이 어떻게 빌드되는지를 보여준다. ADK에 있는 모든 정렬 구현은 모두 동일한 인터페이스를 사용하여 각각을 실험하기가 쉽다. 예를 들어, 다음의 코드는 HEAPSORT의 전체 구현을 나타낸다.

#include "report.h"

/** Heapify the subarray ar[0,max). */
static void heapify (void **ar, 
                     int(*cmp)(const void *,const void *),
                     int idx, int max) {
   int left = 2*idx + 1;
   int right = 2*idx + 2;
   int largest;
 
   /* Find largest element of A[idx], A[left], and A[right]. */
   if (left < max && cmp (ar[left], ar[idx]) > 0) {
      largest = left;
   } else {
      largest = idx;
   }
 
   if (right < max && cmp(ar[right], ar[largest]) > 0) {
      largest = right;
   }
 
   /* If largest is not already parent, swap and propagate. */
   if (largest != idx) {
       void *tmp;
  #ifdef COUNT
  ADD_SWAP;
  #endif /* COUNT */
  
       tmp = ar[idx];
       ar[idx] = ar[largest];
       ar[largest] = tmp;
  
       heapify(ar, cmp, largest, max);
     }
}

/** Build heap within array by repeatedly invoking heapify. */
static void buildHeap (void **ar, 
                       int(*cmp)(const void *,const void *),
                       int n) {
   int i;
   for (i = n/2-1; i>=0; i--) {
      heapify (ar, cmp, i, n);
   }
}

/** Sort the array using Heap Sort implementation. */
void sortPointers (void **ar, int n,
                   int(*cmp)(const void *,const void *)) {
   int i;
   buildHeap (ar, cmp, n);
   for (i = n-1; i >= 1; i--) {
     void *tmp;
  #ifdef COUNT
  ADD_SWAP;
  #endif /* COUNT */
     tmp = ar[0];
     ar[0] = ar[i];
     ar[i] = tmp;
  
     heapify (ar, cmp, 0, i);
   }
}

위의 코드는 다음의 위치에 있다.

$ADKHOME/Code/Sorting/PointerBased/straight_HeapSort.c.

Linux의 time 유틸리티를 이용하여 sample(QUICKSORT를 이용하는) 실행파일을 실행한다.

time ./sample BillText.txt > /dev/null
0.016u 0.004s 0:00.01 100.0%    0+0k 0+0io 0pf+0w

약 1/100초 정도의 시간이 소요되며, 예제의 QUICKSORT가 6배 정도 빠름을 알 수 있다. 하지만 time 유틸리티가 시간을 충분히 정확하게 측정하지 못하다는 것을 알 수 있다. timing.c 드라이버는 더 정확한 시간 측정법을 보여준다. 이 드라이버를 이용하여 동일한 알고리즘에 대한 실행파일을 만들 수 있다.

./quicksort BillText.txt > /dev/null
0.006381seconds

이 프로그램을 20번 실행하여 가장 빠른 것과 가장 느린 것을 제외하면, 평균적으로 0.0066±.0001초 정도 소요되는 것을 알 수 있다. QUICKSORT가 동일 데이터에 대해서 BUCKET SORT에 비해 얼마나 빠른지 확인해 보도록 하자.

./bucketsort BillText.txt > /dev/null
0.019378 seconds

동일하게 20번 실행하여 가장 빠른 것과 가장 느린 것을 제외하고 평균을 내면 약 0.0199±0.0003초 정도 소요된다. 이 데이터에 대해서 BUCKET SORT는 약 3배 정도 느린 것이다.

HEAP SORT는 어떨까? 동일한 20번의 실행(./heapsort BillText.txt > /dev/null)을 통하여 0.0077±.0004초가 소요됨을 확인하였다. 성능은 QUICKSORT와 비슷하지만 그만큼 효율적이지는 않다. 지금까지의 결과를 요약하면 다음과 같다.

알고리즘	12,041 라인의 H.R.1424 법안의 정렬 실행시간 (초)
QUICKSORT	0.0066
HEAP SORT	0.0077
BUCKET SORT	0.0199

실행시간 차이의 원인

이러한 정렬 알고리즘들의 성능을 좀 더 정확한 측정하기 위해, 디버깅 정보를 추가하여 ADK를 다시 컴파일 해보기로 한다. 컴파일러의 COUNT 명령어를 세팅하기 위해 $ADKHOME/Code/Sorting/PointerBased에 있는 Makefile의 아래 라인의 주석을 제거한다.

COUNTCOMPARE = -DCOUNT

그리고 $ADKHOME/Code/Sorting/PointerBased 디렉토리에서 아래의 명령어를 실행한다.

make clean
make

이렇게 다시 컴파일을 함으로써 정렬시 두 원소가 비교되는 횟수와 두 원소가 교환되는 횟수를 알 수 있다. 이제 다시 November_2008 디렉토리로 돌아가서 Makefile을 비슷한 방법으로 COUNTCOMPARE을 –DCOUNT로 수정한 다음, 실행파일을 만들기 위해 아래 명령어를 실행한다.

make clean
make

각각의 실행파일을 한번씩 실행하며, 이제 출력되는 정보가 중요하므로 실행시간은 무시한다.

./quicksort BillText.txt > /dev/null
0.006834 seconds
278237 comparisons, 203246 swaps

./heapsort BillText.txt > /dev/null
0.007580 seconds
285591 comparisons, 150061 swaps

./bucketsort BillText.txt > /dev/null
0.020143 seconds
766933 comparisons, 756554 swaps

위의 결과에서 볼 수 있듯이, 성능에 가장 영향을 끼치는 요소는 데이터들 간 비교 횟수이다. HEAP SORT가 QUICKSORT에 비해 37%나 적게 데이터를 교환하지만 약 10% 정도 느리다. 이러한 차이는 각 알고리즘의 특성에 기인한다. 또한, BUCKET SORT는 QUICKSORT에 비해서 거의 3배 이상 비교 및 4배 정도의 교환을 한다. 따라서, 이 입력 데이터에 대해서는 QUICKSORT가 명백한 승자이다.

주의: 이제 $ADKHOME/Code/Sorting/PointerBased 디렉토리로 돌아가서 데이터 비교 및 교환을 측정하지 않도록 Makefile을 수정 하고 다시 컴파일 해야 한다 (make clean; make). 그렇지 않으면 나중에 성능을 측정할 때 ADK의 성능이 느리게 측정된다. 또한, November_2008 디렉토리에 있는 Makefile도 동일하게 수정하고 다시 컴파일 해야 한다(make clean; make).

이 책에서 필자는 26개의 알파벳으로 이루어진 무작위한 문자열을 변경하는 방법을 이용하여 정렬 알고리즘을 비교한다. 12,041개의 무작위로 선택된 스트링에 대해서 결과를 보기 위해 November_2008 디렉토리에서 make compare 명령을 실행한다. 이 명령어는 ADK 측정 방식을 이용하여 입력 데이터에 대해 20번을 실행하여 평균 실행 시간을 출력한다. 실험 결과를 아래의 표에 도시하였다.

알고리즘	12,041번을 교환하는 실행 시간 (초)
BUCKET SORT	0.0032
QUICKSORT	0.0047
HEAP SORT	0.0066

이 입력 데이터에 대해서는 BUCKET SORT가 가장 좋은 성능을 보인다. 이번에는 왜 그럴까? 한가지 이유는 이번에는 BUCKET SORT가 65,536개 대신에 17,576개의 저장소를 이용했다는 것이다. 하지만 이것이 전부는 아니다. 또 다른 이유는 이번 테스트에서는 12,041개의 스트링이 17,576개의 저장소에 균등하게 배분되었다는 것이다. H.R.1424 법안을 보면 스트링이 표준 분포를 따르지 않음을 알 수 있다. 즉, 각 라인에 단지 537개의 두 글자로 된 접두사가 있기 때문에 65,536개의 저장소가 있더라도 그 중 8%만이 이용될 것이다. 또한, 12개의 저장소에 전체의 25%의 라인이 저장되며, 각각의 저장소에는 200개 이상의 스트링이 저장된다. 가장 많은 스트링이 저장된 저장소에는 524개의 스트링이 저장되었으며, 이 스트링은 영어에서 가장 자주 사용되는 ‘th’로 시작한다.

다른 입력 데이터에 대한 결과

160,136개의 단어가 수록된 영어사전에서 2개에서 13개의 알파벳으로 이루어진 12,041개의 단어를 무작위로 선택하여 정렬을 하면 어떨까? November_2008 디렉토리에서 make wordCompare 명령어를 실행해 보자.

알고리즘	12,041개의 무작위로 선택된 영어 단어의 정렬 실행시간 (초)
BUCKET SORT	0.0048 (50% 증가)
QUICKSORT	0.0053 (13% 증가)
HEAP SORT	0.0083 (26% 증가)

BUCKET SORT가 알파벳을 교환하는 것에 비해 실행 시간이 가장 많이 증가하지만 그래도 가장 성능이 좋다. 이러한 경향이 계속 유지 될까? 대답은 ‘아니다’이다. 다음 실험에서 필자는 13배가 많은 무작위의 영어 단어를 정렬한다. November_2008 디렉토리에서 make dictionaryCompare 명령어를 실행해 보자. QUICKSORT가 확실히 가장 효율적이며, 실행시간 또한 가장 작게 증가함을 알 수 있다.

알고리즘	156,500개의 무작위로 선택된 영어 단어의 정렬 실행시간 (초)
QUICKSORT	0.1456 (30 배 느려짐)
HEAP SORT	0.3052 (58 배 느려짐)
BUCKET SORT	0.3200 (39 배 느려짐)

필자는 위의 정렬 알고리즘의 비교 결과를 얻기 위해서 3개의 서로 다른 입력 데이터를 사용하였다. 입력 데이터에 상관없이 모든 경우에 잘 동작하는 알고리즘은 거의 없다. 책의 4장에서 필자는 각 알고리즘의 장단점을 비교하기 위한 분석 자료와 벤치마크 결과를 소개한다. 또한 필자는 여러분이 각자의 데이터를 이용하여 각 알고리즘을 평가해보기를 기대한다.

마지막 제안: 최적화

주어진 sortPointers 인터페이스에 대해서, 두 개의 원소를 비교하기 위해서 간단히 포인터를 넘겨주는 데에 오버헤드에 대한 한계가 있다. 이러한 성능 평가의 핸디캡을 없앨 수는 없을까? 먼저 다음의 코드를 실행시켜 보자. ./modified_quicksort BillText.txt > /dev/null. modified_baseQsort.c 코드를 보면 알고리즘의 향상 없이 이러한 함수 인자를 사용하지 않고 동일하게 20회 이상의 실행에 대해서 평균적으로 0.0066±.0002초 정도의 성능 향상을 볼 수 있는 방법을 확인할 수 있다. 이를 보면 컴파일러 최적화 옵션 “-O3”이 큰 차이를 느끼지 못하도록 충분히 강력한 것처럼 보인다. 이러한 결과를 보면 효율적인 프로그램을 작성하기 위해서는 최적화를 잘하는 것보다는 범용의 코드 라이브러리에 인자를 주는 방법을 강조해야 함을 알 수 있다.

다음 칼럼

다음의 12월 칼럼에서는 책의 5장의 검색 알고리즘에 대해서 깊이 알아볼 예정이다. 그 때까지 여러분은 Algorithms in a Nutshell 책에 있는 다양한 알고리즘을 공부해 보고, ADK를 통해 제공되는 예제들을 한번 보기를 기대한다.