TimSort源码详解

标签:mergesort   module   logs   包含   init   通过   problems   eve   假设   

Python的排序算法由Peter Tim提出,因此称为TimSort。它最先被使用于Python语言,后被多种语言作为默认的排序算法。TimSort实际上可以看作是mergeSort+binarySort,它主要是针对归并排序做了一系列优化。如果想看Python的TimSort源码,在Cpython的Github仓库能找到,这里面还包含一个List对象的PyList_Sort函数。这篇文章为了方便借用JAVA对TimSort的实现源码来说明其原理。

一.binarySort函数

TimSort非常适合大量数据的排序,对于少量数据的排序,TimSort选择使用binarySort来实现,因此我想先介绍一下binarySort的过程。

我们知道插入排序的思路是通过交换元素位置的方式依次插入元素(如果不太了解插入排序可以先去熟悉一下),当要插入元素时,从已排序的部分的最后一位开始,依次比较其与待插入的元素的值,这样来找到待插入元素的位置。显然,在插入排序的过程中,始终是有一个在增长的有序部分和在缩短的无序部分。排序过程见下图(图源自RainySouL1994的博客):

 技术图片

 但是插入排序有个很明显的问题,在找当前元素的位置时它是一步一步地在有序部分往前推进的,而有序列表的插入可以通过二分法来减少比较次数,这和二分查找的目的不同但是思路相同(可以自己尝试一下实现它),我们称其为二分插入,通过二分插入实现的排序就是二分排序(binarySort)。我们可以看一下它的Java源码:

//a是数组,lo是待排序部分(有序部分+无序部分)的最低位(包含),hi是最高位(不包含),start是无序部分的最低位,c是比较函数即排序的依据
private static <T> void binarySort(T[] a, int lo, int hi, int start, Comparator<? super T> c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {//接下来就是二分插入的过程
        T pivot = a[start];
        int left = lo;
        int right = start;
        assert left <= right;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (c.compare(pivot, a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;
        int n = start - left;//n表示要移动的元素数量
        //优化插入过程,当要移动的元素数量为1或2时,可以直接交换元素位置;
        //否则将left后的元素往后挪一位再插入,方式是通过arraycopy函数复制
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

二.run

这是TimSort中最重要的一个概念,实在找不到合适的翻译(无奈脸)。run实际上就是一个连续上升(包含相等)或者下降(不包含相等)的子串。比如对于数组[1,3,2,4,6,4,7,7,3,2],其中有四个run,第一个是[1,3],第二个是[2,4,6],第三个是[4,7,7],第四个是[3,2],在函数中对于单调递减的run会被反转成递增的序列。源码中通过countRunAndMakeAscending()函数来得到run:

private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, Comparator<? super T> c) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi)
        return 1;

    //找到run的结束位置,如果是下降的序列将其反转
    if (c.compare(a[runHi++], a[lo]) < 0) {
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi);
    } else {
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
            runHi++;
    }

    return runHi - lo;//返回值为run的长度
}

 三.TimSort排序过程

直接上源码分析,可以参考代码注释和下面的解释来阅读:

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) {
    assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

    int nRemaining  = hi - lo;//待排序的数组长度
    if (nRemaining < 2)
        return;  //长度为0或1的数组无需排序

    // 如果数组长度小于32(即MIN_MERGE,TimSort的Python版本里这个值为64),直接用binarySort排序
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);//找到第一个run,返回其长度
        binarySort(a, lo, hi, lo + initRunLen, c);//第一个run已排好序,因此binarySort的参数start=lo+initRunLen
        return;
    }

    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);//最小run长度,见解释A
    do {
        // 找run
        int runLen = countRunAndMakeAscending(a, lo, hi, c);

        // 如果run长度小于minRun,将其扩展为min(nRemaining,minRun)
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen, c);//扩展run到长度force
            runLen = force;
        }

        ts.pushRun(lo, runLen);// 将run保存到栈中,见解释B
        ts.mergeCollapse();// 根据规则合并相邻的run,见解释C

        // 继续寻找run
        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);

    // Merge all remaining runs to complete sort
    assert lo == hi;
    ts.mergeForceCollapse();//最后收尾,将栈中所有run从栈顶开始依次邻近合并,得到一个run
    assert ts.stackSize == 1;
}

 

解释A:在执行排序算法之前,会计算minRun的值,minRun会从[16,32]区间中选择一个数字,使得数组的长度除以minRun等于或者略小于2的幂次方。比如长度是65,那么minrun的值就是17;如果长度是174minrun就是22。minRunLength()函数代码如下:

private static int minRunLength(int n) {
    assert n >= 0;
    int r = 0;      // 如果n的低位有任何一位为1,r就会置1
    while (n >= 32) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

解释B:存run是通过两个栈,分别保存run的起始位置和长度,可以看pushRun()函数代码:

private int stackSize = 0;  // 栈中run的数量
private final int[] runBase;
private final int[] runLen;

private void pushRun(int runBase, int runLen) {
     this.runBase[stackSize] = runBase;
     this.runLen[stackSize] = runLen;
     stackSize++;
}

解释C:这里的合并规则如下:假设栈顶三个run依次为X,Y,Z,X为栈顶run,要求它们的长度满足X+Y<Z及X<Y两个条件。其实这就是TimSort算法的精髓所在了,它通过这样的方式尽力保证合并的平衡性,即让待合并的两个数组尽可能长度接近,从而提高合并的效率。通过这两个条件限制,保证了栈中的run从栈底到栈顶是从大到小排列的,并且合并的收敛速度与斐波那契数列一样。可以看mergeCollapse()函数代码:

private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {//条件一不满足的话,Y就会和X、Z中较小的run合并
            if (runLen[n - 1] < runLen[n + 1])
                n--;
            mergeAt(n);
        } else if (runLen[n] <= runLen[n + 1]) {//条件二不满足的话,Y就和X合并
            mergeAt(n);
        } else {
            break; // Invariant is established
        }
    }
}

四.合并的方式

到这里我们就把整个流程讲完了,还有最后一个问题没有讲--如何合并run?合并两个run需要额外空间(可以不用,但是效率太低),额外空间大小我们可以设为较小的run的长度。假设我们有前后X、Y两个run需要合并,X较小,那么X可以放入临时内存中,然后从小到大合并;如果Y较小,那么把Y放入临时内存,然后从大到小排序。这个流程其实也比较简单(图源自佛西先森的博客):

技术图片

 

 

 并且,由于两个run都是已经排好序的序列,我们可以在run合并之前计算A中最后一个元素在B中的位置i,那么B中i之后的元素都不需要参与合并;同理,我们也可以计算B中第一个元素在A中位置j,A中j之前的元素都不需要参与合并。

在归并排序算法中合并两个数组就是一一比较每个元素,把较小的放到相应的位置,然后比较下一个,这样有一个缺点就是如果A中如果有大量的元素A[i...j]是小于B中某一个元素B[k]的,程序仍然会持续的比较A[i...j]中的每一个元素和B[k],增加合并过程中的时间消耗。

为了优化合并的过程,TimSort设定了一个阈值MIN_GALLOP,如果A中连续MIN_GALLOP个元素比B中某一个元素要小,则通过二分搜索找到A[0]B中的位置i0,把Bi0之前的元素直接放入合并的空间中,然后再在A中找到B[i0]所在的位置j0,把Aj0之前的元素直接放入合并空间中,如此循环直至在AB中每次找到的新的位置和原位置的差值是小于MIN_GALLOP的,这才停止然后继续进行一对一的比较。

五.总结

总结一下上面的排序的过程:

  1. 如果长度小于32直接进行二分插入排序
  2. 遍历数组组成一个run
  3. 得到一个run之后会把他放入栈中
  4. 如果栈顶部几个的run符合合并条件,就会合并相邻的两个run
  5. 合并会使用尽量小的内存空间和GALLOP模式来加速合并

参考资料:1.世界上最快的排序算法——Timsort

      2.JDK8官方源码

TimSort源码详解

标签:mergesort   module   logs   包含   init   通过   problems   eve   假设   

原文地址:https://www.cnblogs.com/hejiayang/p/14119741.html

版权声明:完美者 发表于 2020-12-17 12:27:06。
转载请注明:TimSort源码详解 | 完美导航

暂无评论

暂无评论...