list 컨테이너에 있는 것을 범용 알고리즘을 사용하여 정렬 할 때 어떤 방법이 있는지 설명하고 각 정렬 방식을 사용했을 때 어떤 것이 성능적으로 우수한지 결과를 보여주고 있습니다.

또 아래에는 글에서 소개한 정렬 방식의 구현을 코드로 보여주고 있습니다.

 

 

출처 : http://www.s34.co.jp/cpptechdoc/article/sort/index.html

 

sort는 list를 정렬 할 수 없다.

 

 

표준 C++가 제공하는 <algorithm>에는 편리한 알고리즘이 많이 준비되어 있습니다.

그 중에서도 sort(sort, stable_sort)는 사용 빈도가 높은 알고리즘입니다.

유감스럽지만 sort, stable_sort가 인수로서 받는 이테레이터는 RandomAccessIterator가 아니면 안됩니다. 따라서 list<T>의 요소를 정렬 하고 싶을 때,

list<int> il;
sort(il.begin(), il.end());

라고 하는 코드는 compile error를 일으킵니다. list<T>의 이테레이터는 BidirectionalIterator로 랜덤 접근을 할 수 없기 때문입니다.

list<T>에는 메소드 sort()가 준비되어 있습니다만 코드 중에서 이용하는 컨테이너를 여러가지로 바꾸는 경우

#ifdef USE_LIST
typedef list<int> container;
#else
typedef vector<int> container;
#endif
...
container c;
...
#ifdef USE_LIST
c.sort();
#else
sort(c.begin(), c.end());
#endif

와 같이 #ifdef...#else...#endif로 새로 바꾸지 않으면 안 되게 됩니다.

여기서 Bidirectionaliterator(혹은 ForwardIterator)를 받아들이는 정렬 알고리즘을 준비하면 이러한 변환을 행하지 않고 끝납니다.


selection_sort: 단순 선택 정렬

단순 선택 정렬 알고리즘은 매우 단순합니다.

  1. x[0] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내서 그것과 x[0]을 교환한다
  2. x[1] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내서 그것과 x[1]를 교환한다
  3. x[2] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내 그것과 x[2]를 교환한다

...이것을 N회 반복하면 정렬 완료입니다.

요소의 비교 회수는 N2에 비례하고 교환 회수는 N에 비례합니다.


buble_sort: 버블 정렬

가장 유명하고 가장 성능이 나쁜 정렬입니다.

  1. x[0] )과 x[1] 을 비교하여 x[0] > x[1] 이라면 이 두 개를 교환한다
  2. x[1] 과 x[2] 를 비교하여 x[1] > x[2] 이라면 이 두 개를 교환한다
  3. x[2] 와 x[3]를 비교하여 x[2] > x[3] 이라면 이 두 개를 교환한다

...이것을 N회 반복하면 X[N-1]에는 최대 요소가 저장 됩니다.

그리고 이 일련의 처리 중에서 한 번이라도 교환이 행해지면 최대 요소를 제외한(요소수는 하나 적다) 열에 대해 재차 반복합니다.

요소의 비교 회수/교환 회수 모두 N2에 비례합니다.


comb_sort: 콤 정렬

버블 정렬은 "매우 가까운 두 개의 요소간에 비교/교환을 행한다"는 것이 성능이 좋지 않은 원인입니다. 더 떨어진 요소 사이에 비교/교환을 행하면 더 빨라질 것입니다. 즉, 버블 정렬 알고리즘을 약간 어레인지한:

  1. x[0]와 x[0+gap] 을 비교하여 x[0] > x[0+gap] 이라면 이 두 개를 교환한다
  2. x[1] 과 x[2+gap] 를 비교하여 x[1] > x[2+gap] 이라면 이 두 개를 교환한다
  3. x[2] 와 x[3+gap] 를 비교하여 x[2] > x[3+gap] 이라면 이 두 개를 교환한다

...이 일련의 처리를 gap을 점차 작게 하면서 반복합니다.

정렬에 대해 조사하고 있던 참에 "콤 소트(comb_sort)"라고 하는 알고리즘을 찾아냈습니다. 이것은 상기 알고리즘에 대하여 gap / 1.3 을 새로운 gap으로 반복합니다( 1.3 이라고 하는 값은 경험적으로 구할 수 있던 값인 것 같다).


세 개의 정렬을 비교

상기 세 개의 정렬(selection_sort, bubble_sort, comb_sort)에 대해서 비교/교환 회수를 실측해 보았습니다.

정렬 대상은 list<char> 로 aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
이것을 승순, 즉: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
로 순서를 바꾸는데 행한 비교/교환 회수를 실측했습니다.

알고리즘 비교 회수 교환 회수
단순 선택 정렬 1378 51
버블 정렬 1377 975
콤 정렬 564 99

이 결과로부터도 버블 정렬의 늦음은 분명합니다.
그에 대한 콤 정렬은 단순 선택 정렬/버블 정렬과 비교하면 비교 회수가 격감하고 있습니다.


역자

아래 내용 중 'stable_sort: 안정적인 정렬(only VC++)' 부분은Visual Studio 2008에서 확인 결과 맞지 않습니다. 이 글이 2004년 이전에 써여진 글이기 때문에 지금과는 틀린 것 같습니다. 그러니 이 부분은 그냥 넘어가셔도 됩니다. 또한 comb_sort에 관한 내용은 위키피디아에 있습니다.


stable_sort: 안정적인 정렬(only VC++)

알고리즘 stable_sort 는 표준 C++ 규격에서는 인수에 건네 주는 이테레이터는RandomAccessIterator이다고 쓰여져 있습니다. 하지만 적어도 Visual C++의 STL 구현에서는 헤더<algorithm>의 단 2행을 고쳐 쓰는 것만으로 list<T>에 적용할 수 있는 것을 알 수 있었습니다.

헤더 <algorithm>의 570 행 근처:

template inline
void _Insertion_sort_1(_BI _F, _BI _L, _Ty *) {if (_F != _L) for (_BI _M = _F; ++_M != _L; ) {_Ty _V = *_M; if (!(_V < *_F)) _Unguarded_insert(_M, _V); else {copy_backward(_F, _M, _M + 1); *_F = _V; }}}

및 620 행 근처:

template inline
        void _Insertion_sort_1(_RI _F, _RI _L, _Pr _P, _Ty *)
        {if (_F != _L)
                for (_RI _M = _F; ++_M != _L; )
                        {_Ty _V = *_M;
                        if (!_P(_V, *_F))
                                _Unguarded_insert(_M, _V, _P);
                        else
                                {copy_backward(_F, _M, _M + 1);
                                *_F = _V; }}}

에 있는 {copy_backward(_F, _M, _M + 1);

{_RI _N = _M; copy_backward(_F, _M, ++_N);

로 고쳐 써 주세요.이것만으로 stable_sort 에 BidirectionalIterator 를 건네 줄 수 있게 됩니다.


source code
#include <algorithm>

template <class ForwardIterator,class Predicate>
void selection_sort(ForwardIterator first, ForwardIterator last, Predicate pr)
{
while ( first != last ) { ForwardIterator mid = std::min_element(first, last, pr);
if( first != mid ){ std::iter_swap(first, mid);
}
++first;
}
}

template <class ForwardIterator>
void selection_sort(ForwardIterator first, ForwardIterator last) {
while( first != last ) { ForwardIterator mid = std::min_element(first, last);
if( first != mid ){ std::iter_swap(first, mid);
}
++first;
}
}

template <class BidirectionalIterator,class Predicate>
void bubble_sort(BidirectionalIterator first, BidirectionalIterator last, Predicate pr) {
bool swapped;
do { BidirectionalIterator curr = first; BidirectionalIterator next = curr;
++next; swapped=false;
while( next!= last ) {
if( pr(*next,*curr)) { std::iter_swap(curr, next); swapped = true;
}
++curr;
++next;
}
--last;
} while( swapped );
}

template <class BidirectionalIterator>
void bubble_sort(BidirectionalIterator first, BidirectionalIterator last) {
bool swapped;
do { BidirectionalIterator curr = first; BidirectionalIterator next = curr;
++next; swapped =false;
while( next != last ) {
if(*next <*curr ){ std::iter_swap(curr, next); swapped = true;
}
++curr;
++next;
}
--last;
} while( swapped );
}

template <class BidirectionalIterator, class Predicate>
void comb_sort(BidirectionalIterator first, BidirectionalIterator last, Predicate pr) {
int gap =static_cast<int>(std::distance(first, last));
if( gap < 1 ){
return;
}
     BidirectionalIterator first2 = last;
     bool swapped = false;
     do{
       int newgap = (gap*10+3)/13;
       if( newgap < 1) newgap =1;
       std::advance(first2, newgap - gap);
       gap = newgap;
       swapped = false;
       for( BidirectionalIterator target1 = first, target2 = first2;
               target2 != last;  ++target1, ++target2) {
if( pr(*target2, *target1) ) { std::iter_swap(target1, target2); swapped = true;
          }
}
} while((gap >1)|| swapped );
}

template <class BidirectionalIterator>
void comb_sort(BidirectionalIterator first, BidirectionalIterator last){
       int gap = static_cast<int>(std::distance(first, last));
       if( gap <1 ){  return;}
BidirectionalIterator first2
= last;
bool swapped=false;
do {
int newgap =(gap*10+3)/13;
if( newgap < 1) newgap =1; std::advance(first2, newgap-gap); gap = newgap; swapped =false;
for( BidirectionalIterator target1 = first, target2 = first2; target2 != last;
++target1,++target2){
if(*target2 <*target1 ) { std::iter_swap(target1, target2); swapped =true;
}
}
} while( (gap >1)|| swapped );
}
sample code (상기 코드의 직후에 기술)

#include <iostream>
#include <functional>
#include <list>
using namespace std;
int main() { list<char> il, tl; for ( int i = 0; i < 26; ++i ) { tl.push_back('a'+i); tl.push_back('A'+i); }
il = tl; cout << "source :"; copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "selection (ascending) :"; selection_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "selection (descending):"; selection_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "bubble (acsending) :"; bubble_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "bubble (descending) :"; bubble_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "comb (ascending) :"; comb_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "comb (descending) :"; comb_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl; #ifdef PATCHED_MS_STL il = tl; cout << "stable (ascending) :"; stable_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "stable (descending) :"; stable_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl; #endif return 0; }

result
source                :aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
selection (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
selection (descending):zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
bubble (acsending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
bubble (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
comb (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
comb (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
stable (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
stable (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA


이 글은 스프링노트에서 작성되었습니다.

신고
by 흥배 2009.04.14 01:05

우선 순위 큐를 사용하는 경우 같은 순위의 원소는 들어온 순서대로 하고 싶은데 지멋대로 되는 경우가 있습니다. 이런 경우 커스텀한 우선 순위 큐를 만들어야 되는데 그에 대한 방법을 설명하고 있습니다.

 

 

 

출처 : http://www.s34.co.jp/cpptechdoc/article/stable_pq/index.html

번역 : 최흥배 ( jacking75@gmail.com )

 

 

안정적인 우선 순위 큐



 

queue에 의한 커멘드의 수신과 처리

작은 client/server 시스템의 server측 설계/구현에 관련되게 되었습니다. server에는 복수의 client가 접속되어 각 client로부터 커멘드를 수신하여 커멘드에 응한 처리를 하고 그 결과를 client에 보내줍니다.

 

나는 이 server 어플리케이션을 두 개의 스레드로 실현하려고 생각했습니다. 즉 client로부터 커멘드를 수신하는 R_thread 와 커멘드의 해석/처리/송신을 행하는 S_thread를 기동합니다.
그리고 이 두 개의 스레드 사이에 커멘드를 요소로 하는 queue를 두는 것으로 스레드간의 커멘드 전달을 행하기로 했습니다. server 구현의 아웃라인은 이하와 같이 됩니다:

struct command {
// client로부터 수신한 데이터...
};

std::queue<command> cmd_q; // 커멘드 큐

void R_thread() {
while ( true ) {
command cmd = client로부터 수신한 커멘드;
cmd_q.push(cmd);
}
}

void S_thread() {
while ( true ) {
command cmd = cmd_q.front();
cmd_q.pop();
// cmd 를 처리하고 결과를 송신
}
}

int main()
{
// R_thread 를 기동
// S_thread 를 기동
...
}

설계 도중에 새로운 기능 추가 요구가 굴러 들어왔습니다. 복수의 client 각각 우선 순위를 할당하여 우선 순위가 높은 client로부터의 커멘드는 보다 신속히 처리해 주었으면 한다고 합니다.


priority_queue는 사용할 수 있을까?

STL은 priority_queue라고 하는 문자 그대로 "우선 순위 첨부 queue"를 제공해 주고 있기 때문에 기능 추가에 대응할 수 있도록 조속히 상기 코드를 손보았습니다:

struct command {
// client로부터 수신한 데이터...
int priority; // 우선 순위
};

bool operator<(const command& x, const command& y) {
return x.priority < y.priority;
}

std::priority_queue<command> cmd_q; // 커멘드 큐

... 이하 같이 ...

priority_queue에 요소를 push()하면 pop() 때에 priority가 큰 순서로 꺼낼 수 있습니다. 짧은 시간에 작업은 완료 끝나서 검사 팀에 릴리스 했습니다.

갑자기 검사 팀으로부터 클레임이 뛰어들어 왔습니다.
「client로부터 송신한 복수의 커멘드에 대한 처리 결과가 준 커멘드의 순서대로 되돌아 오지 않는다」라고 합니다.

조속히 작은 테스트 코드를 만들어 그 행동을 검증하기로 했습니다:

struct command {
char code;
int priority;
command(char c, int p) : code(c), priority(p) {}
};

inline bool operator<(const command& x, const command& y) {
return x.priority < y.priority;
}

ostream& operator<<(ostream& strm, const command& c) {
return strm << c.code << ':' << c.priority;
}

int main() {

int i;

cout << "input:" << endl;
for ( i = 0; i < 16; ++i ) cout << command(i/4+'A',i%4) << ' ';
cout << endl;

cout << "output:" << endl;
std::priority_queue<command> pq;
for ( i = 0; i < 16; ++i ) pq.push(command(i/4+'A',i%4));
while ( !pq.empty() ) {
cout << pq.top() << ' ';
pq.pop();
}
cout << endl;

return 0;
}

이 코드의 실행 결과는 이하와 같이 되었습니다

 
input:
A:0 A:1 A:2 A:3 B:0 B:1 B:2 B:3 C:0 C:1 C:2 C:3 D:0 D:1 D:2 D:3
output:
A:3 C:3 B:3 D:3 D:2 B:2 C:2 A:2 A:1 B:1 C:1 D:1 D:0 C:0 B:0 A:0

과연 우선 순위가 높은 커멘드로부터 순서대로 출력되고 있습니다만 우선 순위의 동일한 커멘드에 대해서는 그 차례가 틀려 있습니다.

이렇게 되면 좋습니다...
A:3 B:3 C:3 D:3 A:2 B:2 C:2 D:2 A:1 B:1 C:1 D:1 A:0 B:0 C:0 D:0
 

stable_priority_queue의 구현

그래서 STL이 제공하는 priority_queue에서는 원하는 동작을 기대할 수 없는 것이 밝혀져서 어떠한 대체 수단을 생각하지 않으면 안 되게 되었습니다. 그렇다고는 해도 server의 메카니즘(스레드간의 큐에 의한 커멘드의 전달)을 큰폭으로 변경하고 싶지는 않습니다. "안정" 우선 순위 큐 stable_priority_queue<T> 를 설계/구현하여 priority_queue<T> 와 교환 하기로 했습니다.

stable_priority_queue<T>는 그 내부에 순서 집합 c[0] .. c[N-1] 를 보관 유지시킵니다(N:요소수). 이 순서 집합은 우선 순위에 근거하여 승순(낮은 순서)으로 늘어놓는 것으로 합니다.

요소 x를 삽입할 때는 c[i] >= x (i = 0..N-1)를 채우는 최초의 i의 위치 즉 우선 순위로 정렬 된 순서 집합 내의 적절한 위치에 x를 끼어들게 합니다.

요소를 꺼내는 것은 매우 간단, 순서 집합의 마지막을 꺼내면 된다.

이것으로 완성된거나 다름 없습니다. queue<T> 나 priority_queue<T> 와 인터페이스를 통일하여 stable_priority_queue<T> 를 구현합시다...

#include <algorithm>
#include <iterator>
#include <functional>

template <class T, class Container = std::deque<T>,
class Compare = std::less<Container::value_type> >
class stable_priority_queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
typedef Container container_type;

protected:
Container c;
Compare comp;

private:
template<class InputIterator>
void push(InputIterator first, InputIterator last)
{ for ( ; first != last; ++first ) push(*first); }

public:
explicit stable_priority_queue(const Compare& pp = Compare(),
const Container& cc = Container())
: comp(pp) { push(cc.begin(), cc.end()); }

template <class InputIterator>
stable_priority_queue(InputIterator first, InputIterator last,
const Compare& pp = Compare())
: comp(pp) { push(first,last); }

bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.back(); }
void pop() { c.pop_back(); }

void push(const value_type& x) {
Container::iterator it = c.begin();
while ( it != c.end() && comp(*it, x) ) ++it;
c.insert(it, x);
}
};
 


바이너리 검색에 의한 고속화

이것으로 우선 목적으로 하는 stable_priority_queue<T> 를 만들 수 있었습니다.

하지만 이것에는 약간의 불만이 남습니다. 요소의 삽입 때 내포 하는 컨테이너의 각 요소는 우선 순위에 근거하여 정렬 되고 있으니까 바이너리 검색(바이너리 서치)를 사용하면보다 고속으로 삽입 위치가 요구됩니다.

void push(const value_type& x) {
Container::iterator it = std::lower_bound(c.begin(), c.end(), x, comp);
c.insert(it, x);
}

일반적으로 바이너리 검색은 컨테이너 내의 요소를 랜덤 액세스 하므로 list<T>와 같은 랜덤 액세스 할 수 없는 컨테이너에는 적용할 수 없을 것입니다만 STL의 알고리즘 lower_bound는 랜덤 액세스를 요구하지 않습니다.


stable_priority_queue<T>
#include <algorithm>
#include <iterator>
#include <functional>

template <class T, class Container = std::deque<T>,
class Compare = std::less<Container::value_type> >
class stable_priority_queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
typedef Container container_type;

protected:
Container c;
Compare comp;

private:
template<class InputIterator>
void push(InputIterator first, InputIterator last)
{ for ( ; first != last; ++first ) push(*first); }

public:
explicit stable_priority_queue(const Compare& pp = Compare(),
const Container& cc = Container())
: comp(pp) { push(cc.begin(), cc.end()); }

template <class InputIterator>
stable_priority_queue(InputIterator first, InputIterator last,
const Compare& pp = Compare())
: comp(pp) { push(first,last); }

bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.back(); }
void pop() { c.pop_back(); }

void push(const value_type& x) {
c.insert(std::lower_bound(c.begin(), c.end(), x, comp), x);
}
};
sample code (상기 코드의 직후에 기술)
#include <iostream>
#include <deque>
#include <queue>
#include <list>

using namespace std;

struct command {
char code;
int priority;
command(char c, int p) : code(c), priority(p) {}
};

inline bool operator<(const command& x, const command& y) {
return x.priority < y.priority;
}

ostream& operator<<(ostream& strm, const command& c) {
return strm << c.code << ':' << c.priority;
}

int main() {

int i;

cout << "input sequence:" << endl;
for ( i = 0; i < 16; ++i ) cout << command(i/4+'A',i%4) << ' ';
cout << endl;

cout << "priority_queue(based on vector)" << endl;
std::priority_queue<command> pq;
for ( i = 0; i < 16; ++i ) pq.push(command(i/4+'A',i%4));
while ( !pq.empty() ) {
cout << pq.top() << ' ';
pq.pop();
}
cout << endl;

cout << "stable_priority_queue(using deque)" << endl;
stable_priority_queue<command> spqd;
for ( i = 0; i < 16; ++i ) spqd.push(command(i/4+'A',i%4));
while ( !spqd.empty() ) {
cout << spqd.top() << ' ';
spqd.pop();
}
cout << endl;

cout << "stable_priority_queue(using list)" << endl;
stable_priority_queue<command, list<command> > spql;
for ( i = 0; i < 16; ++i ) spql.push(command(i/4+'A',i%4));
while ( !spql.empty() ) {
cout << spql.top() << ' ';
spql.pop();
}
cout << endl;

return 0;
}
result
input sequence:
A:0 A:1 A:2 A:3 B:0 B:1 B:2 B:3 C:0 C:1 C:2 C:3 D:0 D:1 D:2 D:3
priority_queue(based on vector)
A:3 C:3 B:3 D:3 D:2 B:2 C:2 A:2 A:1 B:1 C:1 D:1 D:0 C:0 B:0 A:0
stable_priority_queue(using deque)
A:3 B:3 C:3 D:3 A:2 B:2 C:2 D:2 A:1 B:1 C:1 D:1 A:0 B:0 C:0 D:0
stable_priority_queue(using list)
A:3 B:3 C:3 D:3 A:2 B:2 C:2 D:2 A:1 B:1 C:1 D:1 A:0 B:0 C:0 D:0

이 글은 스프링노트에서 작성되었습니다.

신고
by 흥배 2009.04.03 11:48
| 1 |