aiwiki.page
中文

Powersort

Powersort 是一种自适应的稳定归并排序方法,根据有序段的位置,为已有序的子序列选择近乎最优的归并顺序。

14 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
归并排序稳定排序排序算法数组(数据结构)二叉树哈夫曼编码栈(数据类型)熵(信息论)Powersort

Powersort 是一种自适应的归并排序方法,能够为有序子序列(称为有序段)选择高效的归并顺序。它由 J. Ian Munro 和 Sebastian Wild 于 2018 年提出,利用相邻有序段的位置和长度,以很低的调度开销构造近乎最优的归并树。它的主要贡献是一种归并策略,即决定何时归并哪些相邻有序段的规则。结合适当的有序段检测和稳定归并操作,它就构成了一种能够利用输入中已有顺序的稳定排序算法。

有序段与归并顺序问题

自然归并排序首先识别输入中已有序的部分。例如,一个数组可能由几个长度相差悬殊的升序段组成。也可以检测降序段并将其反转,但必须妥善处理相等元素,以保持稳定性。

找到有序段后,算法必须决定如何将它们归并。这一选择很重要,因为一个元素所在的有序段在接连参与归并时,该元素可能会被反复复制或比较。

在标准的抽象成本模型中,归并长度为 aa 和 bb 的有序段,成本为 a+ba+b。考虑三个连续的有序段,其长度分别为 44、44 和 88:

  • 先归并前两个有序段,再将结果与第三个有序段归并,成本为 8+16=248+16=24。
  • 先归并后两个有序段,再将结果与第一个有序段归并,成本为 12+16=2812+16=28。

这两种调度方案得到的排序结果相同,但第一种的归并总工作量更小。

在通常对连续有序段进行稳定归并的框架中,只能归并相邻的有序段。因此,归并调度方案对应一棵保序二叉树:它的叶节点按原始的从左到右顺序表示各个原始有序段。如果有序段 ii 的长度为 rir_i,所在深度为 did_i,则归并总成本为

C=∑i=1kridi.C=\sum_{i=1}^{k} r_i d_i.

因此,调度问题就是构造一棵成本较低的有序二叉树,使权重较大的叶节点倾向于处在较浅的深度。

这与霍夫曼编码相似,但普通霍夫曼编码并不保持指定的叶节点顺序。因此,不考虑位置、直接归并最短的两个有序段,并不能作为有效的替代方法。

节点幂

Powersort 为相邻有序段之间的每个边界赋予一个较小的整数,称为节点幂。在概念上对整个输入区间进行均衡细分时,这个整数表示两个有序段在哪一层被分开。

设输入长度为 nn,两个相邻有序段占据的半开区间为

[a,b),[b,c).[a,b), \qquad [b,c).

它们的归一化中点为

x=a+b2n,y=b+c2n.x=\frac{a+b}{2n}, \qquad y=\frac{b+c}{2n}.

它们之间边界的幂是满足下式的最小非负整数 pp:

⌊2px⌋≠⌊2py⌋.\left\lfloor 2^p x\right\rfloor \ne \left\lfloor 2^p y\right\rfloor.

由于两个中点都位于 [0,1)[0,1) 内,首次分离发生在 p≥1p\geq 1 时。

从几何上看,将区间 [0,1)[0,1) 反复二等分。节点幂就是两个中点首次落入不同小区间时的细分层数:

  • 较小的幂表示输入中较高层级的划分。
  • 较大的幂表示更局部的划分,通常应当更早处理。

等价地,节点幂标识了两个中点的二进制展开中首次出现差异的位置;上述基于向下取整的定义可以精确处理落在细分边界上的情况。

节点幂根据原始的相邻有序段计算,而不是在归并后根据当时形成的更大有序段反复重新计算。实现时可以使用整数运算和位运算,无须以浮点数计算中点。

基于栈的调度

Powersort 从左到右处理有序段,同时用一个栈维护待处理的有序段及其边界幂。

从概念上说,其调度过程如下:

  1. 识别下一个有序段。
  2. 计算它与前一个原始有序段之间的边界幂。
  3. 归并那些边界幂大于新边界幂的待处理组。
  4. 保留新边界,继续扫描。
  5. 处理完最后一个有序段后,归并剩余的待处理组。

新遇到的低幂边界意味着一个较高层级的划分。因此,在保留这一边界以供后续处理之前,必须先完成它左侧更局部的归并。

由此得到的调度方案对应一棵以边界幂为依据的笛卡尔树,其中较小的幂更靠近根节点。这就把简单的栈操作过程与预期的层次化归并树联系起来。

对于长度分别为 44、44 和 88 的有序段,其归一化中点分别为 1/81/8、3/83/8 和 3/43/4。两个边界的幂分别为 22 和 11。遇到第二个幂更小的边界时,算法会先归并前两个有序段,再将合并后的有序段与最后一个有序段归并。

栈中的幂保持递增这一不变量,使待处理条目数的上界为 O(log⁡n)O(\log n)。除计算节点幂的成本外,调度所需的工作量与有序段数量呈线性关系。

自适应性与复杂度

Powersort 不仅适应输入的总规模,也适应有序段长度的分布。

对于长度分别为 r1,…,rkr_1,\ldots,r_k 的 kk 个有序段,定义

pi=rin,H=∑i=1kpilog⁡21pi.p_i=\frac{r_i}{n}, \qquad H=\sum_{i=1}^{k}p_i\log_2\frac{1}{p_i}.

这里,HH 是有序段长度分布的信息熵。它衡量输入分散在各个有序段中的程度:各段长度相等时,H=log⁡2kH=\log_2 k;而当一个有序段占据绝大部分输入、其余几个段都很短时,熵可能低得多。

在二路归并成本模型中,nHnH 是任何归并树的加权路径长度的下界,即使不要求保持叶节点顺序也不例外。Powersort 的归并成本满足

C≤nH+2n.C\leq nH+2n.

因此,它的归并成本与最优保序归并成本之差不超过一个线性项。“近乎最优”指的就是这一保证,并不意味着 Powersort 总能选出成本严格最小的树。

如果有序段检测采用线性时间算法,归并采用普通的线性时间算法,则其时间复杂度为

O(n(1+H)),O\bigl(n(1+H)\bigr),

这意味着当 k≥2k\geq 2 时,复杂度为 O(nlog⁡k)O(n\log k),而最坏情况下仍具有通常的 O(nlog⁡n)O(n\log n) 上界。对于已经有序的输入,可以在线性时间内完成识别,无须执行归并。

调度栈需要 O(log⁡n)O(\log n) 的辅助空间。这与归并操作本身所需的内存是分开的:传统的基于数组的稳定实现,总体上可能需要 O(n)O(n) 的临时存储空间。调度栈很小,并不意味着整个排序算法是原地算法。

与蒂姆排序的关系

Powersort 与蒂姆排序采用了相同的实用思路:

  • 检测已有的有序段。
  • 在有益时扩展过短的有序段,通常使用插入排序。
  • 以稳定方式归并相邻有序段。
  • 使用高效的归并例程,其中可能包括疾驰搜索。

两者的核心区别在于归并策略。经典蒂姆排序根据涉及待处理有序段长度的不等式来决定何时归并。Powersort 则使用由有序段位置和长度推导出的边界幂。

由于这种职责分离,可以用 Powersort 的调度方式替换蒂姆排序的归并顺序规则,而无须替换外围的有序段检测、比较处理、临时缓冲区管理或归并机制。

在 CPython 3.11 中,Python编程语言的 list.sort() 和 sorted() 底层实现采用了 Powersort 的归并策略。这一变化针对的是内部调度策略,并未改变公开的排序接口或稳定性保证。因此,将 Python 的排序实现称为蒂姆排序时,也可能是在指一种更广义的实现,其归并调度使用的是 Powersort。

适用范围与局限

Powersort 的数学保证针对的是一种特定成本模型。实际运行时间还取决于元素比较成本、数据移动、分支行为、CPU 缓存效应以及归并实现的细节。

例如,归并长度为 aa 和 bb 的有序段,并不一定恰好进行 a+ba+b 次比较。普通归并最多进行 a+b−1a+b-1 次比较,而疾驰搜索或其他捷径在适宜的数据上可以大幅减少比较次数。因此,最小化抽象归并成本,并不一定能在每种输入上都使比较次数或运行时间最少。

这一保证也只适用于提供给归并策略的那些有序段。扩展短有序段会改变有序段序列,因此在分析完整排序实现时,必须计入扩展操作的成本。

最后,Powersort 是最优保序归并的一种近似方法,而不是精确优化算法。精确方法可以构造成本最低的有序归并树,但需要更复杂的调度机制。Powersort 放弃了精确最优性,换取了一套简洁、从左到右运行且开销较低的过程,同时保证额外归并成本具有线性上界。