深入理解 timsort 算法(1):自适应归并排序

Python 的 timsort 算法出了名的晦涩难懂。这是情理之中的事,它非常复杂。不过,当你真正对它进行深入研究后,你会发现它“只不过”是归并排序的一个变种。这些变异,有的非常巧妙,有的则非常直接明了,总之令人印象颇为深刻。

我会通过一些例子,让你从基本的归并算法(mergesort)开始,逐步过渡到 timsort。在本文中,我将探讨如何实现基本的自适应归并排序算法(adaptive mergesort),该算法是 timsort 的核心。以后的文章会在此基础上,讨论timsort中更多具体的优化。

为了简单起见,我不打算考虑普遍情况,只考虑整型数组(很容易类推到其他类型, 也使得代码更容易理解)。需要说明的是,我将隐藏一些细节(可能会有一些不太严谨的地方)。所以,如果你希望了解算法的具体细节,还是应该参考Tim Peters的说明

对了,例子是 C 写的,Sorry。

那么,我们从最简单的归并算法开始吧。

假定你已经了解归并算法的原理(如果不知道的话,你就得问下度娘)。一起复习下:长度为1的数组是有序的;当数组长度n > 1,则将数组拆分为2部分(通常从数组中间拆分);分别对两部分进行归并排序;然后执行一次合并操作,遍历两个有序数组,依次将较小的元素插入结果数组,最终得到一个较大的有序数组。

上代码:

我没有贴出完整的代码,你可以在github中查看详情。

到了这一步,如果你是C程序员,可能有件让你非常心惊肉跳的事摆在你眼前:每次调用合并函数的时候,都频繁的申请、释放用于合并操作的内存(我们没检查null返回值,这可能也让你很纠结。除非在demo版中,我会在生产代码中检查返回值的,但愿这能让你宽心)。

我们只要稍稍修改一下原型,再封装一下就可以解决这个问题。

现在我们得到一个封装的排序函数,在函数内完成初始化,然后进行递归调用。在timsort中,我们会经常用到这种模式。但是传入工作函数的内存,最终会比直接使用一整块内存块的情况复杂的多。

我们终于得到了一个基本的归并排序。我们得想想:如何优化?

一般来说,我们不可能找到一种万能的优化方案。归并排序的性能非常接近最优化的比较排序(comparison sort)。timsort最关键特性是,它能充分利用数据中的某些共同规律。如果存这种规律,我们就要充分利用。否则,我们只要达到和普通归并排序基本一样的效率就可以了。

如果你看一下归并排序的实现,会发现实际上最主要的工作是合并操作。那优化地方就基本定位合并操作上。这样可以总结出3种优化途径:

能不能提高合并效率?
能不能减少合并次数?
是不是有些情况下,使用其它办法更好,而非归并排序。

毫无疑问,这3个问题的答案都是“Yes”,这些都是归并排序非常基本的优化方法。比如,递归调用中,可以非常方便地根据数组大小,切换合适的排序算法。归并排序是种很好的通用排序算法,但是在数组较小时,常量因素就占主导地位了。通常情况下,数组小于某个大小的时候(通常是七八个左右),归并排序和插入排序性能就差不多了。

这并不是准确意义上timsort的工作方式,但是我们很快会用到插入排序,因此,下面我得插一小段题外话。

简而言之:假定我们有一个长度为n的有序(sorted)数组,在数组尾部还有第n+1个元素的空间。我们将向数组增加一个元素,并且保证最终数组依然是有序的。我们需要为这个元素找到合适的位置,并且将比该元素大的所有元素后移。最显而易见的办法,将新增元素插入到第n+1位置,然后从后向前交换元素,直至新增元素到达正确的位置(当数组规模较大时,这就不一定是最佳方案了。你应该使用二分查找,然后将余下的部分整体后移,从而避免大量比较操作。对于小型数组,这么做应该没什么意义)。

插入排序这样工作:你已将前面k个元素排序。然后用上面提到的方法,向这k个有序元素中插入第k+1个元素,就得到了k+1个有序元素。如此执行,直至数组结尾。
上代码:

那么代码就会变成这样:

你可以在这里查看该版本。

好了,不说题外话,我们继续算法优化的议题。

我们可能减少合并操作吗?

当然,一般情况下是不行的。不过,我们来考虑一些常见情况。

假设我们的数组已经是有序的。我们需要进行多少次合并呢?

原则上来说,是不需要的:数组已经是有序的。什么都不用做。显然,增加一个初始检查算一种方案,确定数组是否已经排序,然后尽快退出。

然而,这会对排序增加一系列额外工作。当情况符合这种情况时,可以获得很大的性能改善(复杂度从最差的O(nlog(n)),降低到O(n));当情况不符合时,就做了很多无用功。那么我们尝试一下,有什么办法既可以检查数组的有序性,当检查失败时,还可以将检查结果充分利用起来。

假设我们有如下数组:

{5, 6, 7, 8, 9, 10, 1, 2, 3}

(暂时不考虑对较小规模数组会采用不同的排序算法。)

我们从哪里分割数组,才能获得最佳的合并效果呢?

显然,已经有两个有序子数组:5~10,还有1~3。直接采用这两个分组就相当完美。

请允许我提出一个全新的方案:

找到原始数据中最长的增长序列作为第一分组,其它数组元素作为第二分组。

当数组可以被分割为若干个有序数组时,这种方案非常有效(即使算不上什么伟大的想法),但这个办法有时候表现却非常糟。试想,如果数组是倒序排列的,会发生什么呢。每次分割的第一个有序子数组长度都是1。也就是说,每个阶段第一个分组都只有一个元素,然后如此递归分割剩下的n-1个元素。显然,时间复杂度是令人失望的O(n^2)。

我们可以人为地将数组前一半元素分成更小的数组来解决这个问题。但是这还是很难令人满意:我们依旧忽略了许多额外工作,而这些都是徒劳无功。

然而,这里的基本思想非常明确:将有序的子数组作为合并时的分组基准。

比较难处理的是我们对第二分组的选择。我们希望合并时两组数据基本平衡,以避免命中最差情况。

为了了解如何解决这些问题,我们后退一步。思考下面略有点特殊的做法,这是标准归并排序的逆操作。

数组被分割为长度为1的段。

如果有超过一个分组,依次将相邻位置分组两两合并,然后覆盖它们原来的位置。

如果我们有数组 {1, 2, 3, 4},那么有:

{{1}, {2}, {3}, {4}}
{{1, 2}, {3, 4}}
{{1, 2, 3, 4}}

可以比较清楚地看到这与标准的归并排序“一样”:我们只是将递归确定下来,用全局内存替代了栈,相当于归并排序的逆操作。显然,这种方式更贴切的说明我们使用有序子串的想法:第一步,我们没有选择将数组分割为长度为1的段,转而将数组分割为一些已经排序的段落。然后我们像上面描述的那样,进行合并。

那么,这就存在一个问题:我们用到了一些额外的无用内存。在原来的归并排序中,空间复杂度为O(log(n))。这里需要O(n)的内存在储存数据。

那为什么我们“仿造”的算法, 内存消耗怎么比原版算法差这么大呢?

好吧,答案是我在他们实际上还是有区别的。最大的区别是原始归并排序的数据分割列表是延迟生成的。我们只生成下一级操作需要的内存,完成操作操作后就立刻释放了这些内存。

换而言之,实际上我们是优先进行合并,而非创建所有的分组。

那么,我们来看看能不能将这个思想转换为一种算法。

第一步: 在每一步中,创建一个新的基础数据分组(在常规的归并排序中,分组只有一个数据项。 在我们上面提到的版本中,分组内为一个有序的子数组)。将它添加到一个数据已经准备好分组的栈中。将栈顶两个分组进行若干次合并,尝试减少栈的高度。如此重复,直到再也没有分组可以合并。通过合并使得整个栈高度下降为1。

这儿有点不太清晰的地方:我们没有明确判定何时进行合并的逻辑。

要想说明这一点,这里就需要更多文字,现有代码也太少了。所以我就给出一个简单答案:随机选取时机。在一般的归并排序中,基本上选取合并操作进行一半时为宜。比如生成的分组有一半已经和之前的合并,比如指定层次有一半合并后的分组已经和之前的合并,等等。这就好比用抛硬币的方法,决定要不要进行合并。

现在,写点代码。

首先,我们封装一些常用的状态。

我们会将 sort_state 指针传入所有用到的函数。

排序的基本逻辑是这样的:

next_partition 返回1则将一个分组入栈,返回0则没有数据可以入栈(换言之,我们已经到达数组结尾)。 然后我们将栈下降一点。最后,当整个数组都进入分组,我们就将栈下降到一个元素。

这样我们就得到第一个自适应版本的归并排序:如果数据中有很多有序的子串,利用它们可以大幅提升效率。如果没有的话,时间复杂度依然为O(n log(n)) (显而易见)

这个“显而易见”的限制是个小小的瑕疵。数据随机化显然可以避免我们明确进行合并的条件。

那么,我们看看有没有更合适的合并条件。一种显而易见的办法是尝试在栈中保持一些常量条件,然后一直合并,直至满足这些常量条件。

更重要的,我们希望这些常量条件,可以保证栈最多不超过log(n)个元素。

那么,我们来考虑下面的恒定条件:每个栈上的元素长度都至少(大于等于)是其栈顶方向下一元素大小的2倍。也就是说栈顶元素最短,下一最短元素是栈底方向下一元素,且其大小至少是栈顶元素的2倍。

这条恒定条件实现了栈元素空间复杂度log(n)的限定。在栈下降的过程中,确实有爆发生成超长runs的趋势。考虑栈中元素长度如下所示:

64, 32, 16, 8, 4, 2, 1

假设我们push一个长度为1的run入栈。我们将会进行如下一些列的合并。

64, 32, 16, 8, 4, 2, 1, 1
64, 32, 16, 8, 4, 2, 2
64, 32, 16, 8, 4, 4
64, 32, 16, 8, 8
64, 32, 16, 16
64, 32, 32
64, 64
128

接下来,为保证合并更加有效率,这种做法就很明显不合适(实际上这是因为这种做法依赖于数组中可能用到的一种数据结构)。现在来看,我们的合并依然非常简陋,这倒不必太担心,我们现在就着手处理这个问题。

有一点十分明确:现在我们栈的最大高度达成共识。假如栈顶元素长度为1,下一个则>=2,再下一个>=4,依次类推。所以栈中所有数据长度为2^n – 1。在64位操作系统上,数组最长可以有 2^64 个元素(这将是一个大得惊人的数组)。我们知道,栈最多需要65个元素就可以适配这个条件。只要再多增加一个栈元素,也就是我们为栈申请66个元素的空间,就不必担心溢出问题。

还有一点很清楚,我们只需要检查栈顶第2个元素大小>= 2 * 栈顶元素大小即可。因为我们只会不断地将满足这个限制条件的数据入栈,而合并操作也仅发生在栈顶两个元素上。

那么,为了满足这个限制条件,我们只要将should_collapse 做如下改写:

看,我们的自适应合并终于搞定了,好耶~

现在我们再回到之前的那个例子,看看之前棘手的问题现在怎么样了。

考虑下面的倒序数组:

5, 4, 3, 2, 1

用我们的自适应归并排序算法来处理会发生什么呢?

runs栈会像下面这样:

{5}
{5}, {4}
{4, 5}
{4, 5}, {3}
{4, 5}, {3}, {2}
{4, 5}, {2, 3}
{2, 3, 4, 5}
{2, 3, 4, 5}, {1}
{1, 2, 3, 4, 5}

这就是一个非常清晰的归并算法。

你知道对逆序数组排序最好的办法是什么?直接对其进行原址逆序啊,你做到了!

对算法进行一个很简单的改进,我们就可以利用这一点。我们已经在查找升序的run了,当没有找到升序run的时候,直接查找降序run,然后对其进行原址逆序,再将其作为一个正序run入栈即可。

我们将查找下一个run的代码改写如下:

类似逆序数组这样的基本情况,排序算法已经可以更好地处理锯齿状波动的数据了。比如,对下面的数据排序:

{1, 2, 3, 4, 5, 4, 3, 2, 1}

我们会有如下的合并:

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}, {1, 2, 3, 4}
{1, 1, 2, 2, 3, 3, 4, 4, 5}

这样就比之前的实现好多了!

对run的生成算法,还有最后一步优化:

在我们提到的归并排序中,我们有一个数组大小界限,对那些较小的数组切换到插入排序。目前我们的自适应排序中没有类似的功能,这也意味着当没有什么数据结构可利用时,我们的版本与常规的归并排序而言并没有什么优势。

回想一下我们的“逆归并排序”,对较小的run切换到插入排序的做法,可以这样理解:与其从大小为1的run开始,我们从大小为INSERTION_SORT_SIZE的run开始,我们用插入排序保证run是有序的。

这就自然让我们的自适应排序发生变化:当我们找到的run长度小于某个最小值时,就用插入排序将其扩展到这个大小。

这就需要我们对next_partition的结尾部分做如下修改:

(其实可以将这段代码写得再具体一点,可读性会更好,我们已经知道得到的数据是有序的,所以我想偷个小懒)

当处理随机数据是,这样应当对性能有所改善,最差不会低于常规的归并排序。

我们现在得到了自适应排序算法,大体上有点timsort“核心”的意思。 Timsort在此基础上还做了大量的优化,它的成功归功于其中很多改进。不过自适应归并排序是这一切的基础。我希望,也打算在以后的文章中研究其余部分。

1 3 收藏 评论

关于作者:alvendarthy

一个热爱生活的家伙! 个人主页 · 我的文章 · 14

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部