c++ STL sort descending 내림차순 정렬

이번 글은 간단한 포스트 입니다.

알고리듬 공부를 하다 보니 sort를 내림차순으로 정렬하는 팁이 있더군요.

일반적인 sort 함수는 오름차순으로 정렬하는 점을 이용해서, 해당 책의 저자는 데이터 입력시 데이터를 음수화 해서 최적화를 시도했습니다.

그걸 보고 문득!!!

C++에서 제공하는 내림차순 정렬 기능과 제안해준 기능의 성능차는 어떻게 될까하는 의문이 생겨서 시험해본 내역 입니다.

 

일반 c++ sort function 을 내림차순으로 실행하려하면 세번째 argument에 옵션을 추가하면 됩니다. sort function의 사용법과 옵션에 관련된 내용은 적합한 링크로 갈음합니다.

http://www.cplusplus.com/reference/algorithm/sort/

sort - C++ Reference

여담으로 간혹 교수님(강사님)들 중 STL의 사용을 지양하라고 가르치시는 분들이 계시죠. 딱히 틀린 가르침은 아닙니다. 예전 컴파일러에 한해서는 결과물의 최적화가 발적화 였거든요. 다른이유는 STL의 메모리 사용은 자동으로 이루어 지기 때문에 잘 모르는 상태로 이용할 경우 독이 되어 C/C++ 언어를 이용하는 이점이 사라지기 때문입니다. 하지만 C++을 하시겠다면 지금이라도 기본적인 사용법과 주의점을 숙지 하시는게 좋습니다.

그럼 이제 중요한 이야기로 넘어가서, 테스트 코드는 아래와 같습니다. 보시면 아시겠지만 대충 만들었습니다. 알고리듬의 시간차를 보려는 것이니 총 50,000회 수행해서 시간 분포를 계산합니다.. 각 회차에서는 1,000,000 회 난수를 발생시켜 vector에 넣고, 이를 Case 1부터 Case 4까지 4가지 방식으로 가공, 정렬 합니다.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

#include <vector>

#include <chrono>

using namespace std;


int main(int argc, char ** argv){

    srand(time(nullptr));

    int cValue = rand();

    vector<int> arr;
    vector<int> tArr;

    chrono::steady_clock::time_point sTime;
    chrono::steady_clock::time_point eTime;

    double nTime;
    double mTime;
    double bTime;
    double cTime;


    for(int tn = 0 ; 50000 > tn ; tn++){
	arr.clear();

	for(int i = 0 ; 1000000 > i ; i++){
	    arr.push_back(rand());
	}

	tArr.clear();
	sTime = chrono::high_resolution_clock::now();
	for(int i : arr){
	    tArr.push_back(i);
	}

	sort(tArr.begin(), tArr.end(), greater<int>());

	eTime = chrono::high_resolution_clock::now();

	nTime = chrono::duration<double, milli>(eTime - sTime).count();

	tArr.clear();
	sTime = chrono::high_resolution_clock::now();
	for(int i : arr){
	    tArr.push_back(-i);
	}

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

	eTime = chrono::high_resolution_clock::now();

	mTime = chrono::duration<double, milli>(eTime - sTime).count();

	tArr.clear();
	sTime = chrono::high_resolution_clock::now();
	tArr = arr;

	sort(tArr.begin(), tArr.end(), greater<int>());

	eTime = chrono::high_resolution_clock::now();

	bTime = chrono::duration<double, milli>(eTime - sTime).count();

	tArr.clear();
	sTime = chrono::high_resolution_clock::now();
	tArr.assign(1000000, 0);
	memcpy(tArr.data(), arr.data(), sizeof(int) * arr.size());

	sort(tArr.begin(), tArr.end(), greater<int>());

	eTime = chrono::high_resolution_clock::now();

	cTime = chrono::duration<double, milli>(eTime - sTime).count();

	cout << tn << " , " << nTime \
	    << " , " << mTime   \
	    << " , " << bTime	\
	    << " , " << cTime << endl;
    }


    return 0;
}

Case 1는 그냥 다른 vector에 만들어진 난수값을 하나씩 복사본에 추가한뒤 내림차순 정렬합니다.

Case 2은 제가 오늘 읽은 책의 저자가 한것처럼, 값을 복사할때 음수 처리하여, 오름차순 정렬합니다.

Case 3와 Case 4는 평소에 궁금하던 것을 확인해 보려고 추가해 봤어요.

Case 3는 원본을 복사본에 복사할때 "="을 이용해서, 중간 과정을 모두 컴파일러에게 맡깁니다.

Case 4는 메모리지상주의 분들이 선호하는 방식이죠. 포인터 형태로 데이터를 읽어 memcpy 함수로 복사했습니다.

구동 결과는 아래 그래프와 같아요.

별로 차이 없을거라고 생각했으나. Case 2가 Case 1보다 빠릅니다...@____@... 컴파일러 개발자들 보고 있나? 그래도 vector를 "="연산자로 바로 복사하거나, memcpy를 이용한 결과와는 크게 차이나지 않습니다.

하고 나니 궁금해 진것...위의 데이터는 데이터 갯수가 1,000,000개죠. 크다고 할순 없으나, 작다고 하기도 애매합니다. 그래서 1,000개의 데이터를 이용해서 다시 한번 구동해 봅니다. 아래 그래프가 그 결과입니다.

이번엔 결과가 많이 다르네요. 이 결과를 메모리지상주의충들이 좋아 합니다. + 컴파일러 개발자들 보고있나?2 memcpy를 이용한 Case 4가 가장 빠르고, Case 3와 Case 1이 뒤를 따릅니다. 그리고 가장 빨랐던 Case2가 가장 빠르죠. 실제 구동 시간의 평균값을 이용한 수치적 분석도 하려다가 그래프로 충분한것 같아서 (별 특이점 없어서) 여기 까지 쓰겠습니다. 마지막으로 실제 구동하실 분이 계실까 싶지만, 데이터 분석에 이용된 m파일( MATLAB or Octave )도 아래와 같이 공유 합니다.

data = dlmread('/Volumes/Sbin_Work/C++Test/sortTest2.result', ",");

%%

hData = zeros(101, 4);

for i = 1 : 4
    hData(:,i) = hist(data(:, i+1), [0 : 1 : 100]);
end

%%

figure;
hold all;
for i = 1 : 4
    plot(hData(:,i), 'LineWidth', 3);
end

legend(' Case 1 ' , ' Case 2 ' , ' Case 3 ' , ' Case 4 ' );

xlim([55 85]);

ylim([0 17000]);

xlabel(' Time (msec) ', 'fontsize', 15);

print('/Volumes/Sbin_Work/C++Test/sortResult.png', '-dpng');

mean(data)

%%
data = dlmread('/Volumes/Sbin_Work/C++Test/sortTest3.result', ",");

%%

hData = zeros(1001, 4);

for i = 1 : 4
    hData(:,i) = hist(data(:, i+1), [0 : 0.001 : 1]);
end

%%

figure;
hold all;
for i = 1 : 4
    plot(hData(:,i), 'LineWidth', 3);
end

legend(' Case 1 ' , ' Case 2 ' , ' Case 3 ' , ' Case 4 ' );

xlim([20 50]);

%ylim([0 17000]);

xlabel(' Time (usec) ', 'fontsize', 15);

print('/Volumes/Sbin_Work/C++Test/sortResult_LC.png', '-dpng');

mean(data)