那些遇到过的问题

改进快速排序

Pal*_*Dot 11 c sorting performance quicksort micro-optimization

如果可能,我如何改进以下快速排序(性能明智).有什么建议？ 

void main()
    {
      quick(a,0,n-1);
    }

    void quick(int a[],int lower,int upper)
    {
       int loc;
       if(lower<upper)
       {
        loc=partition(a,lower,upper);
        quick(a,lower,loc-1);
        quick(a,loc+1,upper);

       }
    }

    /* Return type: int
      Parameters passed: Unsorted array and its lower and upper bounds */

    int partition(int a[],int lower,int upper)
    {
      int pivot,i,j,temp;
      pivot=a[lower];
      i=lower+1;
      j=upper;
      while(i<j)
        {
            while((i<upper)&&(a[i]<=pivot))
            i++;
            while((a[j]>pivot))
            j--;
            if(i<j)
                {
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

        }//end while

        if(pivot>a[j])
        {
             temp=a[j];
             a[j]=a[lower];
             a[lower]=temp;
        }

         return(j);

}//end partition
Run Code Online (Sandbox Code Playgroud)

Swi*_*iss 24

快速排序算法很容易并行化.如果您有多个内核可以使用,您可以看到相当多的加速.根据您的数据集的大小,它可以轻松地为您提供比任何其他优化更快的速度.但是,如果您只有一个处理器或相对较小的数据集,则速度不会太快.

如果这是可能的话,我可以详细说明.

  • +1表示可能会显着提高性能的内容.大! (6认同)

Ale*_*dru 18

  1. 选择一个更好的支点:例如.在三个中间值中,您选择3个(随机)元素并选择枢轴作为中间元素
  2. 当长度(a [])<M(实际上选择M = 9)时,停止排序.在qsort()完成后,应用插入排序,大概需要M*N = O(N).这避免了许多函数调用接近divide-et-impera递归树的叶子.

AnT*_*AnT 15

第一个建议是:用迭代替换其中一个递归调用.我指的是真正的迭代,而不是手动实现的递归堆栈.即,而不是把两个"新"的要求,以quick从quick"循环"您目前的呼叫quick处理递归的一个分支,并调用quick递归处理另一个分支.

现在,如果你确保总是对较短的分区进行真正的递归调用(并使用较长的分区进行迭代),它将保证log N即使在最坏的情况下递归的深度也永远不会超过,即无论你有多好选择你的中位数.

这一切都在qsortGCC标准库附带的算法中实现.看看来源,应该是有用的.

粗略地说,遵循上述建议的更实际的实现可能如下所示

void quick(int a[], int lower, int upper)
{
  while (lower < upper)
  {
    int loc = partition(a, lower, upper);
    if (loc - lower < upper - loc)
    { /* Lower part is shorter... */
      quick(a, lower, loc - 1); /* ...process it recursively... */
      lower = loc + 1; /* ...and process the upper part on the next iteration */
    }
    else
    { /* Upper part is shorter... */
      quick(a, loc + 1, upper); /* ...process it recursively... */
      upper = loc - 1; /* ...and process the lower part on the next iteration */
    }
  }
}
Run Code Online (Sandbox Code Playgroud)

当然,这只是这个想法的草图.没有测试过.再次,看看GCC实现的相同想法.它们还用"手动"递归替换剩余的递归调用,但这不是必需的.

  • @unknown:绝对错误.显然,你完全错过了这一点.这种修改的要点不是性能(可能没有改进),而是堆栈深度的硬限制.在最坏的情况下,最初的实现具有O(N)递归深度.这意味着在输入错误时它会因堆栈溢出而崩溃.我建议的实现再次在递归深度上具有'log2(N)`的*保证*限制.也就是说,例如,在32位平台上,永远不会有超过32级的递归,并且堆栈永远不会溢出. (2认同)

sam*_*wry 10

使用无环算法对小块(<5个元素)进行排序可以提高性能.我找到了一个如何为5个元素编写无环排序算法的例子:http://wiki.tcl.tk/4118

该想法可用于为C中的2,3,4,5个元素生成无循环排序算法.

编辑:我在一组数据上尝试了它,我测得87%的运行时间与问题中的代码相比.在<20个块上使用插入排序在同一数据集上产生了92%.此测量不具有代表性,但可能表明这是一种如何改进快速排序代码的方法.

编辑:此示例代码为2-6个元素写出无循环排序函数:

#include <stdio.h>

#define OUT(i,fmt,...)  printf("%*.s"fmt"\n",i,"",##__VA_ARGS__);

#define IF( a,b, i, block1, block2 ) \
  OUT(i,"if(t[%i]>t[%i]){",a,b) block1 OUT(i,"}else{") block2 OUT(i,"}")

#define AB2(i,a,b)         IF(a,b,i,P2(i+2,b,a),P2(i+2,a,b))
#define  P2(i,a,b)         print_perm(i,2,(int[2]){a,b});

#define AB3(i,a,b,c)       IF(a,b,i,BC3(i+2,b,a,c),BC3(i+2,a,b,c))
#define AC3(i,a,b,c)       IF(a,c,i, P3(i+2,c,a,b), P3(i+2,a,c,b))
#define BC3(i,a,b,c)       IF(b,c,i,AC3(i+2,a,b,c), P3(i+2,a,b,c))
#define  P3(i,a,b,c)       print_perm(i,3,(int[3]){a,b,c});

#define AB4(i,a,b,c,d)     IF(a,b,i,CD4(i+2,b,a,c,d),CD4(i+2,a,b,c,d))
#define AC4(i,a,b,c,d)     IF(a,c,i, P4(i+2,c,a,b,d), P4(i+2,a,c,b,d))
#define BC4(i,a,b,c,d)     IF(b,c,i,AC4(i+2,a,b,c,d), P4(i+2,a,b,c,d))
#define BD4(i,a,b,c,d)     IF(b,d,i,BC4(i+2,c,d,a,b),BC4(i+2,a,b,c,d))
#define CD4(i,a,b,c,d)     IF(c,d,i,BD4(i+2,a,b,d,c),BD4(i+2,a,b,c,d))
#define  P4(i,a,b,c,d)     print_perm(i,4,(int[4]){a,b,c,d});

#define AB5(i,a,b,c,d,e)   IF(a,b,i,CD5(i+2,b,a,c,d,e),CD5(i+2,a,b,c,d,e))
#define AC5(i,a,b,c,d,e)   IF(a,c,i, P5(i+2,c,a,b,d,e), P5(i+2,a,c,b,d,e))
#define AE5(i,a,b,c,d,e)   IF(a,e,i,CB5(i+2,e,a,c,b,d),CB5(i+2,a,e,c,b,d))
#define BE5(i,a,b,c,d,e)   IF(b,e,i,AE5(i+2,a,b,c,d,e),DE5(i+2,a,b,c,d,e))
#define BD5(i,a,b,c,d,e)   IF(b,d,i,BE5(i+2,c,d,a,b,e),BE5(i+2,a,b,c,d,e))
#define CB5(i,a,b,c,d,e)   IF(c,b,i,DC5(i+2,a,b,c,d,e),AC5(i+2,a,b,c,d,e))
#define CD5(i,a,b,c,d,e)   IF(c,d,i,BD5(i+2,a,b,d,c,e),BD5(i+2,a,b,c,d,e))
#define DC5(i,a,b,c,d,e)   IF(d,c,i, P5(i+2,a,b,c,d,e), P5(i+2,a,b,d,c,e))
#define DE5(i,a,b,c,d,e)   IF(d,e,i,CB5(i+2,a,b,c,e,d),CB5(i+2,a,b,c,d,e))
#define  P5(i,a,b,c,d,e)   print_perm(i,5,(int[5]){a,b,c,d,e});

#define AB6(i,a,b,c,d,e,f) IF(a,b,i,CD6(i+2,b,a,c,d,e,f),CD6(i+2,a,b,c,d,e,f))
#define AC6(i,a,b,c,d,e,f) IF(a,c,i, P6(i+2,c,a,b,d,e,f), P6(i+2,a,c,b,d,e,f))
#define AE6(i,a,b,c,d,e,f) IF(a,e,i,CB6(i+2,e,a,c,b,d,f),CB6(i+2,a,e,c,b,d,f))
#define BD6(i,a,b,c,d,e,f) IF(b,d,i,DF6(i+2,c,d,a,b,e,f),DF6(i+2,a,b,c,d,e,f))
#define BE6(i,a,b,c,d,e,f) IF(b,e,i,AE6(i+2,a,b,c,d,e,f),DE6(i+2,a,b,c,d,e,f))
#define CB6(i,a,b,c,d,e,f) IF(c,b,i,DC6(i+2,a,b,c,d,e,f),AC6(i+2,a,b,c,d,e,f))
#define CD6(i,a,b,c,d,e,f) IF(c,d,i,EF6(i+2,a,b,d,c,e,f),EF6(i+2,a,b,c,d,e,f))
#define DB6(i,a,b,c,d,e,f) IF(d,b,i,BE6(i+2,a,b,c,d,e,f),BE6(i+2,c,d,a,b,e,f))
#define DC6(i,a,b,c,d,e,f) IF(d,c,i, P6(i+2,a,b,c,d,e,f), P6(i+2,a,b,d,c,e,f))
#define DE6(i,a,b,c,d,e,f) IF(d,e,i,CB6(i+2,a,b,c,e,d,f),CB6(i+2,a,b,c,d,e,f))
#define DF6(i,a,b,c,d,e,f) IF(d,f,i,DB6(i+2,a,b,e,f,c,d),BE6(i+2,a,b,c,d,e,f))
#define EF6(i,a,b,c,d,e,f) IF(e,f,i,BD6(i+2,a,b,c,d,f,e),BD6(i+2,a,b,c,d,e,f))
#define  P6(i,a,b,c,d,e,f) print_perm(i,6,(int[6]){a,b,c,d,e,f});

#define SORT(ABn,n,...) \
  OUT( 0, ""); \
  OUT( 0, "inline void sort" #n "( int t[" #n "] ){" ) \
  OUT( 2, "int tmp;" ) \
  ABn( 2, __VA_ARGS__ ) \
  OUT( 0, "}" )

void print_perm( int ind, int n, int t[n] ){
  printf("%*.s", ind-1, "");
  for( int i=0; i<n; i++ )
    if( i != t[i] ){
      printf(" tmp=t[%i]; t[%i]=",i,i);
      for( int j=t[i],k; j!=i; k=j,j=t[j],t[k]=k)
        printf("t[%i]; t[%i]=",j,j);
      printf("tmp;");
    }
  printf("\n");
}

int main( void ){
  SORT( AB2, 2, 0,1 )
  SORT( AB3, 3, 0,1,2 )
  SORT( AB4, 4, 0,1,2,3 )
  SORT( AB5, 5, 0,1,2,3,4 )
  SORT( AB6, 6, 0,1,2,3,4,5 )
}
Run Code Online (Sandbox Code Playgroud)

生成的代码3718行:

sort2():    8
sort3():   24
sort4():   96
sort5():  512
sort6(): 3072

pmg*_*pmg 9

尝试另一种排序算法.

根据您的数据,您可以交换内存以提高速度.

根据维基百科

  • 快速排序具有最佳情况O(n log n)性能和O(1)空间
  • 合并排序具有固定的O(n log n)性能和O(n)空间
  • 基数排序具有固定的O(n.<位数>)性能和O(n.<位数>)空间

编辑

显然你的数据是整数.以2.5M的整数范围在[0,0x0fffffff],我的执行基数排序的约4倍的速度作为您实现快速排序的.

$ ./a.out
qsort time: 0.39 secs
radix time: 0.09 secs
good: 2000; evil: 0

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 2560000
#define RANDOM_NUMBER (((rand() << 16) + rand()) & 0x0fffffff)

int partition(int a[], int lower, int upper) {
  int pivot, i, j, temp;
  pivot = a[lower];
  i = lower + 1;
  j = upper;
  while (i < j) {
    while((i < upper) && (a[i] <= pivot)) i++;
    while (a[j] > pivot) j--;
    if (i < j) {
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  if (pivot > a[j]) {
    temp = a[j];
    a[j] = a[lower];
    a[lower] = temp;
  }
  return j;
}

void quick(int a[], int lower, int upper) {
  int loc;
  if (lower < upper) {
    loc = partition(a, lower, upper);
    quick(a, lower, loc-1);
    quick(a, loc+1, upper);
  }
}

#define NBUCKETS 256
#define BUCKET_SIZE (48 * (1 + ARRAY_SIZE / NBUCKETS))

/* "waste" memory */
int bucket[NBUCKETS][BUCKET_SIZE];

void radix(int *a, size_t siz) {
  unsigned shift = 0;
  for (int dummy=0; dummy<4; dummy++) {
    int bcount[NBUCKETS] = {0};
    int *aa = a;
    size_t s = siz;
    while (s--) {
      unsigned v = ((unsigned)*aa >> shift) & 0xff;
      if (bcount[v] == BUCKET_SIZE) {
        fprintf(stderr, "not enough memory.\n");
        fprintf(stderr, "v == %u; bcount[v] = %d.\n", v, bcount[v]);
        exit(EXIT_FAILURE);
      }
      bucket[v][bcount[v]++] = *aa++;
    }
    aa = a;
    for (int k=0; k<NBUCKETS; k++) {
      for (int j=0; j<bcount[k]; j++) *aa++ = bucket[k][j];
    }
    shift += 8;
  }
}

int ar1[ARRAY_SIZE];
int ar2[ARRAY_SIZE];

int main(void) {
  clock_t t0;

  srand(time(0));
  for (int k=0; k<ARRAY_SIZE; k++) ar1[k] = ar2[k] = RANDOM_NUMBER;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    quick(ar1, 0, ARRAY_SIZE - 1);
  } while (0);
  double qsort_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    radix(ar2, ARRAY_SIZE);
  } while (0);
  double radix_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  printf("qsort time: %.2f secs\n", qsort_time);
  printf("radix time: %.2f secs\n", radix_time);

  /* compare sorted arrays by sampling */
  int evil = 0;
  int good = 0;
  for (int chk=0; chk<2000; chk++) {
    size_t index = RANDOM_NUMBER % ARRAY_SIZE;
    if (ar1[index] == ar2[index]) good++;
    else evil++;
  }
  printf("good: %d; evil: %d\n", good, evil);

  return 0;
}
Run Code Online (Sandbox Code Playgroud)

Kei*_*all 6

关于quicksort的维基百科文章有很多想法.

  • ...一堆通用*理论*的想法,但不幸的是几乎没有实际的(这是可以理解的,因为文章必须是实现/语言独立). (4认同)

归档时间：

查看次数：

8090 次

最近记录：

7 年，9 月 前
相关归档
为什么函数指针和数据指针在C/C++中不兼容？ 128
结构包装是否具有确定性？ 42
核心文件大小限制对进程具有非确定性影响 14
在C中,主要不是一个功能？ 13
Python @property与方法性能 - 使用哪一个？ 12
如何加速此循环(在C中)？ 11
在C++中快速添加随机变量 10
.NET ILMerged程序集的性能 7
Golang自定义排序比本机排序更快 6
在java中排序？ 1
难疑归档
如何撤消Git中最近的提交？ 20327
__str__和__repr__之间的区别？ 2545
抽象函数和虚函数有什么区别？ 1526
如何强制使用favicon刷新？ 1499
在Android上旋转活动重启 1341
如何使用jQuery获取元素的ID？ 1320
如何删除旧的Docker容器 1162
什么是Python 3相当于"python -m SimpleHTTPServer" 1124
如何在div中垂直对齐文本？ 1102
使用node.js作为简单的Web服务器 1068