Sorting efficiency study: sort() is faster than qsort().

天泪离星

/*---------------------------------------------------------------------------
File name: sort-efficiency.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/29/2007 17:40:41
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------
I was asked "Which sorting algorithm is most efficient for random data?".

Analysis:
---------------------------------------------------------------------------
In this article, we consider four approaches of sorting:
1. STL sort + function pointer;
2. STL sort + functor;
3. STL sort;
4. qsort.
A few ouputs are shown in the Sample ouput section. We conclude that:
a. approach 2 is as efficient as approach 3. The former is more flexible,
since you can define what it means by "a>b" yourself.
b. approach 1 takes longest time to finish. Thus you may want to avoid using
function pointers.
c. approach 4 is less efficient than approach 2 and 3. Or we can conclude,
legacy C code is less efficient than standard C++ code.

Sample output:
---------------------------------------------------------------------------
Test #1, size of input is 13388000
Function pointer: 6.549 seconds.
Functor: 4.166 seconds.
Standard C++: 4.166 seconds.
qsort: 6.559 seconds.
Test #2, size of input is 18258761
Function pointer: 9.073 seconds.
Functor: 5.728 seconds.
Standard C++: 5.718 seconds.
qsort: 8.463 seconds.
Test #3, size of input is 12957326
Function pointer: 6.329 seconds.
Functor: 3.995 seconds.
Standard C++: 3.996 seconds.
qsort: 5.939 seconds.
Test #4, size of input is 12806571
Function pointer: 6.229 seconds.
Functor: 3.936 seconds.
Standard C++: 3.965 seconds.
qsort: 5.799 seconds.
Test #5, size of input is 10091271
Function pointer: 4.847 seconds.
Functor: 3.064 seconds.
Standard C++: 3.085 seconds.
qsort: 4.536 seconds.
Test #6, size of input is 13669040
Function pointer: 6.679 seconds.
Functor: 4.196 seconds.
Standard C++: 4.196 seconds.
qsort: 6.209 seconds.
Test #7, size of input is 18539801
Function pointer: 9.233 seconds.
Functor: 5.818 seconds.
Standard C++: 5.829 seconds.
qsort: 8.572 seconds.
Test #8, size of input is 12031356
Function pointer: 5.828 seconds.
Functor: 3.676 seconds.
Standard C++: 3.665 seconds.
qsort: 5.408 seconds.
Test #9, size of input is 16859086
Function pointer: 8.342 seconds.
Functor: 5.287 seconds.
Standard C++: 5.258 seconds.
qsort: 8.262 seconds.
Test #10, size of input is 19100681
Function pointer: 9.503 seconds.
Functor: 5.999 seconds.
Standard C++: 5.999 seconds.
qsort: 8.932 seconds.

Reference:
---------------------------------------------------------------------------
1. Scott Meyers, Effective C++, Effective STL, etc.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <ctime>
#include "hjns.h"
#include <cstdio>
#include <cstdlib>
using namespace std;
inline int cmp(const void* a, const void *b)
{
return *(int*)(a)-*(int*)(b);
}
inline bool funcPointer(int a, int b)
{
return a>b;
}
struct functor : public binary_function<int, int, bool>
{
bool operator()(int a, int b)
{
return a>b;
}
};

int main()
{
int i;
for(i=1; i<11; ++i)
{
hj::number::random rd;
// size if random between 10000000 and 20000000, inclusive.
int kSize = rd(10000000, 20000000);
int* a = new int[kSize];
// generate a random array consisting of 1..kSize
hj::number::randPerm(a, kSize);
// make all four input data sets the same
vector<int> v1(a, a+kSize);
vector<int> v2(a, a+kSize);
vector<int> v3(a, a+kSize);
cout<<"\nTest #"<<i<<", size of input is "<<kSize<<endl;
// function pointer approach
{
clock_t start(clock());
sort(v1.begin(), v1.end(), funcPointer);
clock_t elapsed = clock() - start;
cout<<"Function pointer: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// functor approach
{
clock_t start(clock());
sort(v2.begin(), v2.end(), functor());
clock_t elapsed = clock() - start;
cout<<"Functor: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// standard C++
{
clock_t start(clock());
sort(v3.begin(), v3.end(), greater<int>());
clock_t elapsed = clock() - start;
cout<<"Standard C++: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// qsort (legacy C library function)
{
clock_t start(clock());
qsort((void*)a, kSize, sizeof(int), cmp);
clock_t elapsed = clock() - start;
cout<<"qsort: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
delete [] a;
}
return 0;
}

封xin封mg

哈哈，HJIN，你真的很爱研究这样的问题，很佩服。

我也把我知道的不多的说下。

从测试的结果其实就很能说明了.

qsort 和 sort 采用的都是优化过的快速排序。
但是在qsort那个时代，c++的模板技术还没出来，而sort采用了functor，这样的模板技术大大的加速的排序，而qsort仍然是通过自定义函数，传指针的方式工作。

所以从代码里发现了，如果给sort传一个函数指针，那么运行效率与qsort一样的，如果通过重载传入functor，那么效率就会很大提高。

至于采用模板技术为什么比调用函数快，那就要靠HJIN再研究给予说明了。我就只知道这么点！不知对否哈！

月半弯

It is more about "inline your fuctions".

In approach 2 and 3, there are no function calls since the code is written directly inside "sort()";
In approach 1 and 4, you got the function call overhead.

︶ㄣ帅々︷`

但是如果用inline function不是一样可以在调用点展开吗？这样效果不等同吗？

宝贝

inline function 就不一样了嘛~~~
它省去了函数调用的开销，但是带来了函数展开的内存开销~~~
但是我估计不是inline的问题~~因为在SORT中，有好多循环，用inline是得不常失的（理论上哈~~）
不过编译器在内部做了什么手脚，可能也可以使它的性能增加也不一定哦~~~

女装批发3

struct functor : public binary_function<int, int, bool>
{
bool operator()(int a, int b)
{
return a>b;
}
};
比传函数指针快一些，这个到和我想的不一样。