改进快速排序

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

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)) j--; if(ia[j]) { temp=a[j]; a[j]=a[lower]; a[lower]=temp; } return(j); }//end partition 

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

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

  1. 选择一个更好的支点:例如。 在三个中间值中,您选择3个(随机)元素并选择枢轴作为中间元素
  2. 当长度(a [])

第一个建议是:用迭代替换其中一个递归调用。 我指的是真正的迭代,而不是手动实现的递归堆栈。 也就是说,而不是quick进行两次“新”调用,“回收” 当前调用以quick处理一个递归分支,并quick递归调用以处理另一个分支。

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

这一切都是在GCC标准库附带的qsort算法中实现的。 看看源代码,它应该是有用的。

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

 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 */ } } } 

当然,这只是这个想法的草图。 未经测试。 再次,看看GCC实现的相同想法。 它们还用“手动”递归替换剩余的递归调用,但实际上并不是必需的。

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

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

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

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

 #include  #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 

生成的代码3718行:

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

尝试另一种排序算法。

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

根据维基百科

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

编辑

显然你的数据是整数。 对于[0,0x0fffffff]范围内的2.5M整数,我的radix-sort实现速度大约是快速排序实现速度的4倍。

 $ ./a.out
 qsort时间:0.39秒
基准时间:0.09秒
好的:2000; 邪恶:0
 #include  #include  #include  #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 

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

  1. 您可以通过使用带有显式堆栈的QuickSort来消除recuriosn开销

     void quickSort(int a[], int lower, int upper) { createStack(); push(lower); push(upper); while (!isEmptyStack()) { upper=poptop(); lower=poptop(); while (lower 
  2. 您可以使用更好的枢轴选择技术,例如:

    1. 中位数为3
    2. 中位数的中位数
    3. 随机枢轴

目前最广泛使用的quicksort是在Java的DualPivotQuicksort.java中实现的。所以你可以简单地遵循这种方法,你会看到一个很好的性能改进:

  • 对小数组使用插入排序(47是Java中使用的数字)
  • 使用双枢轴快速排序选择5的第2和第4个元素作为两个枢轴
  • 考虑对运行已排序数字的数组使用mergesort

或者如果你想增加一点复杂性,那么编写一个3轴快速排序 。

如果这不仅仅是为了学习使用stdlib.h中的qsort

根据你的代码,当排序长度为10时,最深的堆栈看起来像

 #0 partition (a=0x7fff5ac42180, lower=3, upper=5) #1 0x000000000040062f in quick (a=0x7fff5ac42180, lower=3, upper=5) #2 0x0000000000400656 in quick (a=0x7fff5ac42180, lower=0, upper=5) #3 0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=8) #4 0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=9) #5 0x00000000004005c3 in main 

除了算法本身,如果我们考虑系统行为,例如堆栈活动,除了正常的调用堆栈成本(推/弹)之外的其他东西可能会大幅降低性能,例如上下文切换,如果是多任务系统,你知道大多数操作系统是多任务,并且堆栈越深,切换成本越高,加上缓存未命中或cachline边界。

我相信在这种情况下,如果长度变大,与其他排序算法相比,你会失败。

例如,当长度达到40时,堆栈可能看起来像(可能更多的条目,如下所示):

 #0 partition (a=0x7fff24810cd0, lower=8, upper=9) #1 0x000000000040065d in quick (a=0x7fff24810cd0, lower=8, upper=9) #2 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=10) #3 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=14) #4 0x0000000000400684 in quick (a=0x7fff24810cd0, lower=4, upper=14) #5 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=4, upper=18) #6 0x0000000000400684 in quick (a=0x7fff24810cd0, lower=0, upper=18) #7 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=26) #8 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=38) #9 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=39) #10 0x00000000004005ee in main 

堆栈太深了。

函数内联也很有用,但它增加了最终可执行文件的代码占用空间。 我同意@Swiss,并行编程可能会对你有所帮助。

完全愚蠢的答案,但…在发布模式下编译代码并打开优化!

首先要做的是对它进行基准测试。 并根据标准qsort和c ++ std :: sort和std :: stable_sort进行基准测试。

如果您的数据集足够大,您的结果将显示std :: sort在所有情况下都优于qsort, 除了那些std :: stable_sort优越的情况。 这是因为std :: sort是模板化的,因此可以内联比较。

您的代码内联比较,因为它不是通用的。 如果您的代码比qsort慢,那么您就遇到了问题。

更快的排序是并行排序部件,例如openmp,然后将它们合并在一起。

从我回答问题的答案复制而来。

编辑:这篇文章假设你已经做了一些明显的事情,比如利用尾递归来摆脱不必要的调用开销。

人们喜欢用某些输入批评快速排序表现不佳, 特别是当用户控制输入时。 以下方法产生匹配中点选择的性能,但随着列表大小的增加,预期复杂度指数地接近O( n log n )。 根据我的经验,由于在大多数情况下开销要少得多,因此它明显优于最佳选择。 它应该对“预期”输入的中点选择均匀执行,但不容易受到输入不良的影响。

  • 使用随机正整数I初始化快速排序。 该值将在整个排序过程中使用(不必生成多个数字)。
  • 选择Pivot作为I mod SectionSize

为了获得额外的性能,您应该始终将快速排序切换为“小”列表段的shell排序 – 我已经看到从15到100的长度被选为截止值。

multithreading?

 /* * multiple-thread quick-sort. * Works fine on uniprocessor machines as well. */ #include  #include  #include  /* don't create more threads for less than this */ #define SLICE_THRESH 4096 /* how many threads per lwp */ #define THR_PER_LWP 4 /* cast the void to a one byte quanitity and compute the offset */ #define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width))) typedef struct { void *sa_base; int sa_nel; size_t sa_width; int (*sa_compar)(const void *, const void *); } sort_args_t; /* for all instances of quicksort */ static int threads_avail; #define SWAP(a, i, j, width) { int n; unsigned char uc; unsigned short us; unsigned long ul; unsigned long long ull; if (SUB(a, i) == pivot) pivot = SUB(a, j); else if (SUB(a, j) == pivot) pivot = SUB(a, i); /* one of the more convoluted swaps I've done */ switch(width) { case 1: uc = *((unsigned char *) SUB(a, i)); *((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); *((unsigned char *) SUB(a, j)) = uc; break; case 2: us = *((unsigned short *) SUB(a, i)); *((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); *((unsigned short *) SUB(a, j)) = us; break; case 4: ul = *((unsigned long *) SUB(a, i)); *((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j)); *((unsigned long *) SUB(a, j)) = ul; break; case 8: ull = *((unsigned long long *) SUB(a, i)); *((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); *((unsigned long long *) SUB(a, j)) = ull; break; default: for(n=0; nsa_base; int n = sargs->sa_nel; int width = sargs->sa_width; int (*compar)(const void *, const void *) = sargs->sa_compar; register int i; register int j; int z; int thread_count = 0; void *t; void *b[3]; void *pivot = 0; sort_args_t sort_args[2]; thread_t tid; /* find the pivot point */ switch(n) { case 0: case 1: return 0; case 2: if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) { SWAP(a, 0, 1, width); } return 0; case 3: /* three sort */ if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) { SWAP(a, 0, 1, width); } /* the first two are now ordered, now order the second two */ if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) { SWAP(a, 2, 1, width); } /* should the second be moved to the first? */ if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) { SWAP(a, 1, 0, width); } return 0; default: if (n > 3) { b[0] = SUB(a, 0); b[1] = SUB(a, n / 2); b[2] = SUB(a, n - 1); /* three sort */ if ((*compar)(b[0], b[1]) > 0) { t = b[0]; b[0] = b[1]; b[1] = t; } /* the first two are now ordered, now order the second two */ if ((*compar)(b[2], b[1]) < 0) { t = b[1]; b[1] = b[2]; b[2] = t; } /* should the second be moved to the first? */ if ((*compar)(b[1], b[0]) < 0) { t = b[0]; b[0] = b[1]; b[1] = t; } if ((*compar)(b[0], b[2]) != 0) if ((*compar)(b[0], b[1]) < 0) pivot = b[1]; else pivot = b[2]; } break; } if (pivot == 0) for(i=1; i 0) ? SUB(a, 0) : SUB(a, i); break; } } if (pivot == 0) return; /* sort */ i = 0; j = n - 1; while(i <= j) { while((*compar)(SUB(a, i), pivot) < 0) ++i; while((*compar)(SUB(a, j), pivot) >= 0) --j; if (i < j) { SWAP(a, i, j, width); ++i; --j; } } /* sort the sides judiciously */ switch(i) { case 0: case 1: break; case 2: if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) { SWAP(a, 0, 1, width); } break; case 3: /* three sort */ if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) { SWAP(a, 0, 1, width); } /* the first two are now ordered, now order the second two */ if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) { SWAP(a, 2, 1, width); } /* should the second be moved to the first? */ if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) { SWAP(a, 1, 0, width); } break; default: sort_args[0].sa_base = a; sort_args[0].sa_nel = i; sort_args[0].sa_width = width; sort_args[0].sa_compar = compar; if ((threads_avail > 0) && (i > SLICE_THRESH)) { threads_avail--; thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid); thread_count = 1; } else _quicksort(&sort_args[0]); break; } j = n - i; switch(j) { case 1: break; case 2: if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) { SWAP(a, i, i + 1, width); } break; case 3: /* three sort */ if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) { SWAP(a, i, i + 1, width); } /* the first two are now ordered, now order the second two */ if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) { SWAP(a, i + 2, i + 1, width); } /* should the second be moved to the first? */ if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) { SWAP(a, i + 1, i, width); } break; default: sort_args[1].sa_base = SUB(a, i); sort_args[1].sa_nel = j; sort_args[1].sa_width = width; sort_args[1].sa_compar = compar; if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) { threads_avail--; thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid); thread_count = 1; } else _quicksort(&sort_args[1]); break; } if (thread_count) { thr_join(tid, 0, 0); threads_avail++; } return 0; } void quicksort(void *a, size_t n, size_t width, int (*compar)(const void *, const void *)) { static int ncpus = -1; sort_args_t sort_args; if (ncpus == -1) { ncpus = sysconf( _SC_NPROCESSORS_ONLN); /* lwp for each cpu */ if ((ncpus > 1) && (thr_getconcurrency() < ncpus)) thr_setconcurrency(ncpus); /* thread count not to exceed THR_PER_LWP per lwp */ threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP); } sort_args.sa_base = a; sort_args.sa_nel = n; sort_args.sa_width = width; sort_args.sa_compar = compar; (void) _quicksort(&sort_args); }