网上的文章当提到std::sort和qsort的区别时，通常把它们的性能差异归因于qsort的反引用开销，我们在这里通过实验来测试看看是不是这样，并且判断std::sort的算法是否有较之于qsort代码更优的性能，或者反过来。         测试用的源代码如下： main.cpp 主函数所在的文件 #include <stdio.h>#include <stdlib.h>#include <time.h>#include <string.h>#include <algorithm>#include "m_qsort.cpp"#include "funcs.h" using namespace std; #define N 1000000 int comp(const void* a,const void* b){ return *(int*)a-*(int*)b;} void main(){ int i,j,*a,*b; clock_t st,et,tt[3]={0}; a=(int*)malloc(sizeof(int)*N); b=(int*)malloc(sizeof(int)*N);  getchar(); for (i=0;i<10;i++) {  m_srand((long)time(NULL));  for (j=0;j<N;j++) a[j]=m_rand();     memcpy(b,a,N*sizeof(int));  st=clock();  qsort(b,N,sizeof(int),comp);  et=clock();  tt[0]+=(et-st);     memcpy(b,a,N*sizeof(int));  st=clock();  m_qsort2(b,N);  et=clock();  tt[1]+=(et-st);   memcpy(b,a,N*sizeof(int));  st=clock();  sort(b,b+N);  et=clock();  tt[2]+=(et-st); } printf("qsort %d ms\n",tt[0]/10); printf("m_qsort2 %d ms\n",tt[1]/10); printf("sort %d ms\n",tt[2]/10);  getchar();} funcs.hvoid m_srand(long seed);int m_rand(); m_qsort.cpp  用于测试qsort修改版的代码 #include <algorithm>using namespace std; /* Always compile this module for speed, not size */#pragma optimize("t", on) /* prototypes for local routines */template<class _RanIt>static void __cdecl shortsort(_RanIt *lo, _RanIt *hi); #define CUTOFF 8            /* testing shows that this is good value */ #define STKSIZ (8*sizeof(void*) - 2)   template<class _RanIt>void m_qsort (    _RanIt base,    size_t num    ){    _RanIt lo, hi;              /* ends of sub-array currently sorting */    _RanIt mid;                  /* points to middle of subarray */    _RanIt loguy, higuy;        /* traveling pointers for partition step */    size_t size;                /* size of the sub-array */    _RanIt lostk[STKSIZ], histk[STKSIZ];    int stkptr;                 /* stack for saving sub-array to be processed */     if (num < 2)        return;                 /* nothing to do */     stkptr = 0;                 /* initialize stack */     lo = base;    hi = base +num-1;        /* initialize limits */ recurse:     size = hi - lo + 1;        /* number of el's to sort */     /* below a certain size, it is faster to use a O(n^2) sorting method */    if (size <= CUTOFF) {        shortsort(lo, hi);  //_Insertion_sort(lo,hi+1);    }    else {         mid = lo + size / 2;      /* find middle element */         /* Sort the first, middle, last elements into order */        if (*lo>*mid) {            iter_swap(lo, mid);        }        if (*lo>*hi) {            iter_swap(lo, hi);        }        if (*mid>*hi) {            iter_swap(mid, hi);        }         loguy = lo;        higuy = hi;         for (;;) {             if (mid > loguy) {                do  {                    loguy ++;                } while (loguy < mid && *loguy<=*mid);            }            if (mid <= loguy) {                do  {                    loguy ++;                } while (loguy <= hi && *loguy<=*mid);            }             /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,               either loguy > hi or A[loguy] > A[mid] */             do  {                higuy --;            } while (higuy > mid && *higuy> *mid);             if (higuy < loguy)                break;             iter_swap(loguy, higuy);             if (mid == higuy)                mid = loguy;        }         higuy ++;        if (mid < higuy) {            do  {                higuy --;            } while (higuy > mid && *higuy==*mid);        }        if (mid >= higuy) {            do  {                higuy --;            } while (higuy > lo && *higuy==*mid);        }         if ( higuy - lo >= hi - loguy ) {            if (lo < higuy) {                lostk[stkptr] = lo;                histk[stkptr] = higuy;                ++stkptr;            }                           /* save big recursion for later */             if (loguy < hi) {                lo = loguy;                goto recurse;           /* do small recursion */            }        }        else {            if (loguy < hi) {                lostk[stkptr] = loguy;                histk[stkptr] = hi;                ++stkptr;               /* save big recursion for later */            }             if (lo < higuy) {                hi = higuy;                goto recurse;           /* do small recursion */            }        }    }     --stkptr;    if (stkptr >= 0) {        lo = lostk[stkptr];        hi = histk[stkptr];        goto recurse;           /* pop subarray from stack */    }    else {        return;                 /* all subarrays done */ }} template<class _RanIt>static void __cdecl shortsort (    _RanIt *lo,    _RanIt *hi    ){    _RanIt *p, *max;     while (hi > lo) {        /* A[i] <= A[j] for i <= j, j > hi */        max = lo;        for (p = lo+1; p <= hi; p ++) {            /* A[i] <= A[max] for lo <= i < p */            if (*p>*max) {                max = p;            }        }         iter_swap(max, hi);         hi --;    }} m_rand.cpp 用于生成0~0x00ffffff之间随机数的代码 static long holdrand; void m_srand(long seed){ holdrand=seed;} int m_rand(){ return ((holdrand = holdrand * 214013L + 2531011L) & 0x00ffffff);}                 主函数分成三段测试代码，每段测试一个函数：qsort、m_qsort、std::sort。其中m_qsort是复制qsort的代码过来然后修改而成。测试数据共有10组，取平均值输出。下面我们开始测试。         先测试qsort和std::sort两个函数，把另外两段测试代码注释掉以节约时间： qsort 1156 mssort 860 ms         实验证明，std::sort比qsort快25.6%。我们把N扩大为两倍2000000，即数组大小扩大成两倍，测试结果： qsort 2416 mssort 1828 ms         实验结果表明在数据增长成两倍的时候，qsort运行时间增长为原来的2.09倍；sort增长为原来的2.13倍。sort算法的增长速度稍快。         std::sort比qsort快25.6%，到底快在哪里呢？我们现在来看看。我们修改了qsort，成为m_qsort，它使用了模板，不需要传入函数指针，而且换掉了原来低效的逐个字节交换的swap函数，用iter_swap代替。比较三个函数： qsort 1131 msm_qsort 640 mssort 857 ms         我们发现，经过对qsort函数进行修改之后，它竟然比sort函数快25.3%！这说明qsort函数的主要开销在于直接对字节指针的操作。这同时也说明，对于基本没有重复键的数据来说，qsort比sort要快。         我们再来比较一下特殊情况。使用系统自带的srand函数和rand函数，生成0~0x00007fff的数，这样1000000个数中就会每个数平均有31个重复值。我们看一下运行结果： qsort 894 msm_qsort 519 mssort 554 ms         可以清楚地看到，在数据重复比较多的时候，sort的性能明显得到了提高。考虑一种极限情况，所有数据相同，我们修改代码再运行一次： qsort 72 msm_qsort 42 mssort 24 ms         这次很明显了，对于重复数据，sort函数的处理能力明显强于qsort。这主要是和sort函数三路划分分得更细致有关。         我们接着考虑递增和递减数组。修改代码然后测试，结果如下： qsort 497 msm_qsort 234 mssort 203 ms         sort函数的运行时间比m_qsort要少。我们可以看到，相比随机数据，有序数据在快速排序的时候得到了很好的优化。再来看递减的数组。 qsort 534 msm_qsort 261 mssort 338 ms         递减数组中sort函数略逊于qsort改进版，这大概是因为sort函数取样9个点造成过多交换开销造成的。         从整体上看，我们得出这样一个结论：对于随机基本无重复的数据，qsort的改进版比sort函数优秀；而sort函数由于对分区比较细致，所以处理重复数据较多的数组则会比较优化。而我们平常所遇到的数据，比如出生年月，性别等，都有很多的重复值，所以sort函数就成为了排序这些数据的首选。

评论