工程排序

美团点评送外卖
美团点评送外卖   发布于 2018-10-22 20:54
阅读量: 124

Engineering a Sort Function 论文解读

在从美团实习离职前夕,参加了一个TiDB的学习组织,接手的第一篇paper就是这个工程化排序。主要是研究快排的算法优化思路和Unix 系统中的Qsort设计

@雪梨教育全体工作人员 为啥不让我传PDF ???? exm???? 

函数接口定义

void sort(void * arr,int en,int es,int(*cmp)(void* ,void*))

void* 的数组指针等同于 GO 里面的 interface{} 或者Java 内的 Object 

en element number 即有多少元素需要排序

es element memory size 即 element 在内存中占用多少字节

cmp 函数用于比较大小的 ,相等返回 0 大 a > b 返回 1 a < b 返回 -1 

当然还有一个替换算法

void swap(void* i,void * j,int n)
{
   do{
      void * t = i;
      *i++ = *j;
      *j++ = t
   }while(--n > 0);
}

这个算法也很简单,将两个序列进行交换,即将Array 1 的数组放入 Array 2 的数组内,当然这个算法主要是在内存上直接操作指针,将内存块i和内存块j的数据交换

简单快排

核心思想为,将一个序列中位数设为基准,比他大的放在右边,比他小的放在左边,然后将序列进行分治递归,并依旧按照这个规则进行整理,最终排序完成

def : iisort(void * a , int n ,int (*cmp)(void * a ,void * b)) as the common pop sort

定义了iisort直接排序一个序列,并且使用一个cmp 函数来进行比较。

那么一个简单的二分快排就可以写出来了

void iqsort0(int *a, int n)
{
          int i, j;
          if (n <= 1) return;
          for (i = 1, j = 0; i < n; i++)
              if (a[i] < a[0])
                  swap(++j, i, a);
          swap(0, j, a);
          iqsort0(a, j);
          iqsort0(a+j+1, n-j-1);
}

这里的swap是将array内的两个索引位置的内容交换

算法的思想是找到一个基准,把他比他小的数放到他的左边,把比他大的数放到他的右边,那么首先对于一个输入序列,首先就要干这个事情,如果直接排序,那么基本就不用排了,就是一个归并排序,也不叫快排了。

首先基准找到的是0,那么肯定要把所有的比array[0]  小的数放在array[0]的左边,只需要一个循环即可搞定,这里的i是递增的索引用于扫描序列,而j是用来记录位置的,哪一位是比基准小的,如果第i位比0位小,直接交换i和j ,一趟循环过后,j已经记录了最远的小于0位的内容的位置,同时循环中也将小于0位的内容移动到了序列的左半部分,最后交换0和j的位置即可,这样就能保证第0位内容在第j+1位置上,并且左半部分都是比他小的,右半部分都是比他大的。

如上图所示,我们知道只要第i位小于0位那么将j位和i位交换,交换的结果是i位数据跑到了j位上,j位递增,那么这个时候0位元素并没有动。

再简单来说,选择第0位作为基准,我们只需要保证比他小的数在他前面就可以了,j只是记录的是哪位比他小,换的时候把i位换到了j+1位,因为为了保证基准不动,不然的话这个基准每次都在动,永远也做不出有效的划分。

举例来说 有序列  [8,1,2,3,4,5,10,15,18,20,200] => 第一

次处理完成应该是 [1,2,3,4,5,8,15,18,20,200] 也就是我们利用j 找到了0位元素真正应该在的位置。

 

通常对Qsort 的优化都是给个随机的基准。

void iqsort1(int *a, int n)
{
int i, j;
    if (n <= 1) return;
    i = rand() % n;
    swap(0, i, a);
    i = 0;
    j = n;
    for (;;) {
        do i++; while (i < n && a[i] < a[0]);
        do j--; while (a[j] > a[0]);
        if (j < i) break;
        swap(i, j, a);
    }
    swap(0, j, a);
    iqsort1(a, j);
    iqsort1(a+j+1, n-j-1);
}

退出循环的条件是 j < i ,我们考察循环内部,j 指针应该指向的是从 右半部分小于第0位元素的元素,同理i是指向第一个大于的,然后当j 和 i 到达临界条件的时候,退出循环,如果不相等,那么直接交换。

这个算法依旧是让第0位作为基准,虽然在进入循环的时候改了一下第0位的元素,其实这样的做法很简单,主要是为了让分割更均匀,最理想情况就是我们的分割点是中位数即把序列平分为两个子序列,然后再递归,这样可以避免一些不必要的递归,至于为什么要避免,那么需要各位研究一下了。也许我下面就会解释了

选择合适的分割点

首先给出每条指令的处理时间消耗

大概是这样的一个关系,我们发现耗时的操作基本就是这个比较的过程,交换内存啥的根本不再一个数量级,毕竟一条xchg汇编就能搞定的事情。

通过上面的一些代码,我们发现了优化快排的思路就是,我们尽可能让我们的基准接近一个序列的中位数,也就是左子序列和右子序列的长度最好差不多,这样就可以达到一个nlogn的最坏复杂度,因为目前的统计来看大概都是 1.386nlogn 的复杂度。

回归最原始的数据,从长度为三的序列开始考虑如何找到中位数的。有了上面的决策树,代码应该很好写出来的。复杂度是log3 基本就是常数的复杂度

那么对于一个序列来说,我们找到了一个从三个元素中寻找中位数的算法,我们知道这三个中位数应该是序列三个子序列的中位数才可以,根据贪心理论。所以最后的med3算法找到了一个全序列的中位数,一定是将序列分成了五份,这个很简单。

         pm = a + (n/2)*es;    /* Small arrays, middle element */
          if (n > 7) {
              pl = a;
              pn = a + (n-1)*es;
              if (n > 40) {    /* Big arrays, pseudomedian of 9 */
                  s = (n/8)*es;
                  pl = med3(pl, pl+s, pl+2*s, cmp);
                  pm = med3(pm-s, pm, pm+s, cmp);
                  pn = med3(pn-2*s, pn-s, pn, cmp);
              }
              pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */
          }

这篇论文提出了这样的一个计算中位数的方法。可以让最后比较次数结果更接近nlogn ,具体的实验结果请看论文。

 

对于相等的选择

一个序列不可能是不重复的集合,一定是可重复的序列,那么最大的时间消耗是比较的消耗,现在开始优化相等的消耗,简单来说,在扫描中如果相等,那么不交换的话是不是可以少操作一次呢?

当然最主要的任务还是要减少比较的次数,也就是和基准相等的数统统扔到中间去,扔完了以后只处理和基准不同的左右两半数组即可。

 

最后的结果为

也就是我们只需要处理 arr[a...c] 和 arr[b...d] 即可,这样对于相等的元素直接不参加下次快排了,之前的版本快排只找到了基准以后分别快排,我们优化了中位数寻找算法,这些相等的元素根本用不上接着排,那还排什么排,直接排和基准不想等的两个序列不就好了吗。

void iqsort2(int *x, int n)
      {
          int a, b, c, d, l, h, s, v;
          if (n <= 1) return;
          v = x[rand() % n];
          a = b = 0;
          c = d = n-1;
          for (;;) {
              while (b <= c && x[b] <= v) {
                  if (x[b] == v) iswap(a++, b, x);
                  b++; 
              }
              while (c >= b && x[c] >= v) {
                  if (x[c] == v) iswap(d--, c, x);
                  c--;
              }
              if (b > c) break;
              iswap(b++, c--, x);
          }
          s = min(a, b-a);
          for(l = 0, h = b-s; s; s--) iswap(l++, h++, x);
          s = min(d-c, n-1-d);
          for(l = b, h = n-s; s; s--) iswap(l++, h++, x);
          iqsort2(x, b-a);
          iqsort2(x + n-(d-c), d-c);
}

这样就好了,最后我们只需要排和基准不想等的两部分就可以了

更多的优化请看论文吧。

 

 

收藏 转发 评论