40-2-라.정렬

리스트는 임의 접근 반복자를 제공하지 않으므로 정렬 속도가 대단히 느린 편이다. 그래서 sort 알고리즘 함수를 사용하지 못하며 대신 sort 멤버 함수를 사용해야 한다. sort 알고리즘은 임의 접근을 활용하는 퀵 소트로 구현되어 있는데 비해 리스트의 sort 멤버 함수는 리스트에 좀 더 특화된 알고리즘으로 작성되어 있다. 두 개의 원형이 제공된다.

void sort();

void sort(BinPred op);

인수를 받지 않는 sort 멤버 함수는 < 연산자로 노드를 비교하여 정렬하며 조건자를 받아들이는 sort 멤버 함수는 조건자의 비교 결과대로 정렬한다. 다음 멤버 함수는 연속된 중복 요소를 제거하는데 같은 이름의 전역 함수도 있지만 멤버 함수는 리스트의 링크 구조를 활용하도록 구현되어 있다.

void unique();

void unique(UniPred op);

간단한 예제로 두 함수를 테스트해 보자.

예 제 : listsort

#include <Turboc.h>

#include <iostream>

#include <list>

using namespace std;

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

void main()

{

const char str[]="stllistcontainer";

list<char> li(&str[0],&str[sizeof(str)-1]);

dump("원본",li);

li.sort();

dump("sort후",li);

li.unique();

dump("unique후",li);

}

문자의 리스트를 생성하고 정렬과 중복 원소 제거를 차례대로 해 보았다.

원본 ==> s t l l i s t c o n t a i n e r

sort후 ==> a c e i i l l n n o r s s t t t

unique후 ==> a c e i l n o r s t

문자 코드의 값을 기준으로 정렬되며 정렬 후 같은 문자가 두 번 이상 연속적으로 나오면 뒤쪽의 문자들이 삭제된다.

리스트는 임의 접근 반복자를 제공하지 않아 일반 알고리즘을 적용할 수 없지만 sort 멤버 함수는 리스트의 링크를 최대한 활용하여 정렬을 수행한다. 그러나 아무래도 임의 접근이 가능한 반복자에 비해 비교와 교환 방법에 제약이 가해지므로 속도 차이는 날 수밖에 없다. 과연 벡터에 비해 어느 정도 느린지 속도 테스트를 해 보자.

예 제 : sortspeed

#include <Turboc.h>

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

using namespace std;

const unsigned NUM=1000000;

void main()

{

randomize();

vector<int> vi;

list<int> li;

int i;

clock_t start;

for (i=0;i<NUM;i++) {

vi.push_back(random(100));

li.push_back(random(100));

}

cout << "키를 누르면 벡터를 정렬합니다." << endl;

getch();

start=clock();

sort(vi.begin(),vi.end());

cout << "벡터 정렬완료. 소요시간 = " << clock()-start << endl;

cout << "키를 누르면 리스트를 정렬합니다." << endl;

getch();

start=clock();

li.sort();

cout << "리스트 정렬완료. 소요시간 = " << clock()-start << endl;

}

정수형의 벡터와 리스트에 100만개의 난수를 넣어 놓고 정렬해 보았다. 시스템 속도에 따라 결과는 다르겠지만 상대적인 속도는 측정 가능하다. 개발툴과 빌드 모드에 따라서도 속도 차이가 많이 벌어지는데 단, 디버그 모드에서는 반복자의 유효성을 점검하는 코드로 인해 공정한 비교가 되지 않으므로 반드시 릴리즈 모드에서 실행해야 한다.

컴파일러	비주얼 C++ 6.0	비주얼 C++ 8.0	Dev-C++
벡터	220	280	891
리스트	2924	1222	3455

보다시피 리스트가 벡터에 비해 작게는 4배 많게는 10배도 더 느리게 정렬된다. 요소 개수가 많아지면 차이는 더 벌어질 것이다. 정렬은 비교와 교환이 굉장히 빈번한 알고리즘이므로 조금이라도 속도를 높이려면 임의 접근이 가능해야 한다. 꼭 필요할 경우는 이 멤버 함수로 리스트를 정렬할 수는 있지만 정렬이 필요한 자료를 리스트에 저장하는 것은 애초에 선택이 잘못된 것이다.

여기서 STL 설계의 비일관성을 엿볼 수 있는데 리스트가 구조적인 문제로 임의 접근 반복자를 제공하지 못해 정렬이 비효율적이라면 sort 멤버 함수도 아예 제공하지 않는 것이 바람직하다. 이 멤버 함수가 제공되면 내부 구조를 잘 모르는 사람은 리스트도 정렬이 잘 되는 것으로 착각하고 리스트를 정렬하려고 들 것이다. STL은 이런 비효율을 방조하고 있는 것이다. 그래도 꼭 필요할 때는 쓸 수 있어야 하므로 없는 것보다 낫다고 한다면 벡터에 push_front를 제공하지 말아야 할 이유도 전혀 없는 셈이다.