Month: August 2013

STL set/priority_queue의 속도 비교

STL을 조금 사용한 분이라면, STL의 set의 속도가 꽤나 느리다는 것을 알고 있을 것이다.

난 이 점을 고려해서 set 대신 priority_queue를 쓸 수 있는 상황이라면 priority_queue를 항상 써왔었는데, 아는 후배로부터 priority_queue가 오히려 set보다 느리다는 이야기를 듣게 되어 한번 실험을 해 보게 되었다.

실험 내용은 단순하다, set으로, priority_queue로 한번씩 정렬을 해 본 다음 거기에 걸리는 시간을 비교하는 것이다. 코드 내용은 아래와 같다.

#include<stdio.h>
#include<queue>
#include<set>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define datatype pair<double, double>

set<datatype> s;
priority_queue<datatype> p;
vector<datatype> data;
datatype tmpdata;

void data_gen(){
	double dd = 1.0;
	int i;
	datatype d;
	for(i = 0; i < 1000000; i++){
		dd = (rand() % 1000000) * (rand() % 1000000);
		if(dd > 10.0 || dd < -10.0)
			dd /= 100;

		d.first=  dd;
		dd = 1.5 + dd * dd - 1.0 / dd;
		if(dd > 10.0 || dd < -10.0)
			dd /= 100;

		d.second = dd;

		data.push_back(d);
	}
}
void sort_pq(){
	printf("sort_q beg\n");
	int i;
	for(i = 0; i < data.size(); i++)
		p.push(data[i]);
	while(!p.empty())
	{
		tmpdata  = p.top();
		p.pop();
	}
}
void sort_set(){
	printf("sort_set beg\n");
	int i;
	for(i = 0; i < data.size(); i++)
		s.insert(data[i]);
	set<datatype>::const_iterator iend = s.end();
	for(set<datatype>::const_iterator itr = s.begin(); itr != iend; itr++){
		tmpdata  = *itr;
	}
	s.clear();
}
void run(void (*func)()){
	clock_t startt = clock();
	func();
	clock_t endt = clock();
	printf("time diff : %lf\n", (endt- startt) / (double)CLOCKS_PER_SEC);
}
int main(){
	data_gen();
	printf("datagen end..\n");

	run(sort_set);
	run(sort_pq);
	return 0;
}

정렬을 할 데이터 타입은 pair<double, double>로 했는데, 이유는 다음과 같다.

(1) set이나 priority_queue에서 pair간의 비교를 하려면 오버로드된 operator를 불러야 하고, double간의 대소 비교 또한 코스트가 크다. 이는 지나치게 비교를 많이 하는 data structure에 강한 패널티를 줄 것이다.
이것은 set에 약간 더 큰 패널티를 줄 것으로 예상하는데, 이유는 priority_queue가 Binary heap으로 되어 있을 경우 높이가 정확히 log_2 N 밖에 되지 않지만 set은 RBTree로 이루어 졌을 경우 height가 더 높을 것이기 때문이다.
(2) integer과는 달리 pair<double, double>은 만약 value copy가 일어날 경우 16바이트나 복사를 해야 하는데, 이는 적어도 여러 instruction을 거쳐야 이루어진다. 이는 값 복사가 너무 많이 일어나는 data structure에 강한 패널티를 줄 것이다.
이것은 priority_queue에 좀 더 큰 패널티를 줄 것으로 예측하는데, RBtree는 노드 삽입을 할 때만 value copy가 일어나고 order를 맞출 때는 전혀 value copy를 쓰지 않지만 Binary heap은 (priority_queue가 배열로 구현되어 있다고 가정할 시) heap 내 order를 맞출 때 여러 번의 value copy가 일어날 수 있기 때문이다.

 

set으로 sorting을 할 때는 iterator를처음부터 끝까지 돌면서 global 변수에 값복사를 한 번 하는 행동을 반복 하였다.

priority_queue로 sorting을 할 때는 top(), pop()을 번갈아가면서 부르면서 아까 말한 global 변수에 값복사를 한 번 하는 행동을 반복하였다.
둘 다 sorting이 끝났을 때 텅 비어있도록 하기 위해서 마지막에 set.clear()를 호출해 주었다.

g++, g++ -O2, VC++2010 Debug, VC++2010 Release에서 각각 돌려보았는데, 결과는 상당히 재미있었다 -_-;

 

1. G++

datagen end..
sort_set beg
time diff : 2.788000
sort_q beg
time diff : 3.670000

보다시피 priority_queue가 더 느렸다.

2. G++ -O2

datagen end..
sort_set beg
time diff : 1.628000
sort_q beg
time diff : 1.283000

둘 다 빨라졌으나 set이 약간 더 느렸다.

3. MSVC++2010 Debug

datagen end..
sort_set beg
time diff : 26.297000
sort_q beg
^C

priority_queue를 10여분동안 켜두었으나 무려 끝나지가 않았다..

4. MSVC++ 2010 Release

datagen end..
sort_set beg
time diff : 1.721000
sort_q beg
time diff : 0.585000

priority_queue가 3배 가량 빨랐다.

 

요약을 하자면, 컴파일러가 optimize를 하지 않았을 땐 set이 더 빠르나 optimize를 했을 땐 priority_queue가 더 빠른 속도를 보였다.

하긴 priority_queue는 set보다 할 수 있는게 더 적은데 얘가 더 느리면 안되지 -_-;;

여하튼 독특한 경험이었다.