至顶网›软件频道 ›基础软件›深入分析qsort库函数（三）－－测试结果

深入分析qsort库函数（三）－－测试结果

扫一扫
分享文章到微信
扫一扫
关注官方公众号
至顶头条

网上的文章当提到std::sort和qsort的区别时，通常把它们的性能差异归因于qsort的反引用开销，我们在这里通过实验来测试看看是不是这样，并且判断std::sort的算法是否有较之于qsort代码更优的性能，或者反过来。

作者：抚耳摸丝来源：CSDN 2008年3月20日

测试用的源代码如下：

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.h
void 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 ms
sort 860 ms

实验证明，std::sort比qsort快25.6%。我们把N扩大为两倍2000000，即数组大小扩大成两倍，测试结果：

qsort 2416 ms
sort 1828 ms

实验结果表明在数据增长成两倍的时候，qsort运行时间增长为原来的2.09倍；sort增长为原来的2.13倍。sort算法的增长速度稍快。