频道栏目
首页 > 网络 > 云计算 > 正文

TimeSort-自适应的、稳定的、自然的合并

2018-05-16 14:18:04      个评论    来源:九师兄  
收藏   我要投稿

TimeSort-自适应的、稳定的、自然的合并

这描述了一个自适应的、稳定的、自然的合并,称为timsort(嘿,我赢得了它)。它在许多类型的部分有序数组中具有超自然的性能(小于lg(N!)的比较需要,并且很少有N-1),但是和Python之前的高度调优的samplesort混合在随机数组中一样快。

简单地说,主要的例行程序在数组上来回移动一次,从左到右,交替地标识下一个运行,然后将其合并到前面的运行“智能”。其他一切都是速度的复杂性,以及一些来之不易的内存效率度量。

与Python的Samplesort Hybrid进行比较

timsort需要一个包含多达N//2指针的临时数组,这意味着在32位的boxes上有2*N的额外字节。在对随机数据进行排序时,可以期望它需要一个temp数组;对于具有重要结构的数据,它可能不需要使用任何额外的堆内存。这似乎是反对它的最有力的论据,但是与一个对象的大小相比,2个临时字节(也可以是随机数据的期望)并不会让我感到害怕。

事实证明,Perl正在转向一个稳定的mergesort,并且它的代码
看起来总是需要一个具有至少N个空间的临时阵列
指针。(请注意,即使空间不是,我也不想这样做
问题; 我相信它在记忆节俭上的努力也可以节省时间
重要的指针复制成本,并使其工作量更小
组。)

+生成随机数组大约四个小时,然后对它们进行排序
在这两种方法下,样本比例需要大约1.5%的比较
(程序在这个文件的末尾)。

+在现实生活中,随机阵列的速度可能会更快或更慢
samplesort取决于平台怪癖。由于它少了
比较平均而言,可以预料到越多越好
昂贵的比较功能是。OTOH,它可以做更多的数据移动
(指针复制)比samplesort,这可能会否定其小
比较优势(取决于平台怪癖)除非比较
是非常昂贵的。

+在具有多种预先存在的订单的阵列上,这会打击样本
的水。即使在某些情况下,它比samplesort快得多
病例样本是特别包裹鼻涕的。我相信这个名单
在现实生活中很多时候都有可利用的偏序,而这就是事实
支持timsort最有力的论据(实际上,samplesort的特例
极端的部分顺序是由真正的用户赞赏,并timsort去
比那些更深入,特别是自然地覆盖每个案件在哪里
有人建议“,如果list.sort()有一个特殊的话,它会很酷
这种情况也……也是……“)。

+下面是sortperf.py中所有测试的确切比较计数,
当运行参数“15 20 1”时。

列键:
*排序:随机数据
\排序:降序数据
/排序:升序数据
3sort:升序,然后3次随机交易
+排序:升序,然后在最后10个随机
排序:许多重复
=排序:全部相等
!排序:最坏的情况

首先是微不足道的情况,对于samplesort而言是微不足道的,因为它是特殊的
他们,并timsort微不足道,因为它自然运行。中
一个“n”块,第一行给出由samplesort完成的比较次数,
第二行是timsort,第三行是百分比
样本数量超过timsort计数:

  n \ sort / sort = sort

32768 32768 32767 32767 samplesort
32767 32767 32767 timsort
0.00%0.00%0.00%(samplesort - timsort)/ timsort

65536 65536 65535 65535
65535 65535 65535
0.00%0.00%0.00%

131072 131072 131071 131071
131071 131071 131071
0.00%0.00%0.00%

262144 262144 262143 262143
262143 262143 262143
0.00%0.00%0.00%

524288 524288 524287 524287
524287 524287 524287
0.00%0.00%0.00%

1048576 1048576 1048575 1048575
1048575 1048575 1048575
0.00%0.00%0.00%

这些算法在这些情况下实际上是相同的,除此之外
timsort在\ sort中做一个比较少的比较。

现在更有趣的案例。lg(n!)是信息论
限制最好的任何基于比较的排序算法都可以做到
平均值(跨所有排列)。当方法显着时
在这之下,它要么是天文学上的幸运,要么就是寻找可利用的
数据结构。

  n lg(n!)* sort 3sort + sort%sortsort!sort

32768 444255 453096 453614 32908 452871 130491 469141旧
448885 33016 33007 50426 182083 65534新
0.94%1273.92%-0.30%798.09%-28.33%615.87%%来自新的

65536 954037 972699 981940 65686 973104 260029 1004607
962991 65821 65808 101667 364341 131070
1.01%1391.83%-0.19%857.15%-28.63%666.47%

131072 2039137 2101881 2091491 131232 2092894 554790 2161379
2057533 131410 131361 206193 728871 262142
2.16%1491.58%-0.10%915.02%-23.88%724.51%

262144 4340409 4464460 4403233 262314 4445884 1107842 4584560
4377402 262437 262459 416347 1457945 524286
1.99%1577.82%-0.06%967.83%-24.01%774.44%

524288 9205096 9453356 9408463 524468 9441930 2218577 9692015
9278734 524580 524633 837947 2916107 1048574
1.88%1693.52%-0.03%1026.79%-23.92%824.30%

1048576 19458756 19950272 19838588 1048766 19912134 4430649 20434212
19606028 1048958 1048941 1694896 5832445 2097150
1.76%1791.27%-0.02%1074.83%-24.03%874.38%

案件讨论:

*排序:随机数据中没有结构可供利用,所以理论上
限制是lg(n!)。两种方法都接近,timsort拥抱
它(事实上,从边缘角度看,这是一个惊人的进步 -
timsort知道,在撞墙之前只剩下1%左右
好的做的比较,不会支付随机数据 - 但如此
做samplesort混合)。相比之下,霍尔的原始随机枢纽
快速排序与限制相比约有39%多,中位数为3
变体约增加19%。

3sort,%排序,和!排序:没有比赛; 这个数据有结构,但是
而不是特定种类样本的特殊情况。请注意结构
不是故意放在那里的 - 它是为最坏的情况而制作的
之前的快速排序实现。这timsort指甲它来了
对我感到惊讶(尽管在回顾中显而易见)。

+排序:samplesort特殊情况下的这种数据,并做少了几个比较
比timsort。但是,timsort在所有情况下运行速度明显更快
因为timsort在合并业务中,所以我们有时间限制
运行效率很高,而samplesort在这方面做了更多的数据移动
(为它)的特殊情况。

排序:samplesort针对大量相等元素的特例是
对sort的特定数据模式非常有效,而timsort就是这样
不会接近,尽管这显然已经成为现实
重复出现的好处很多(比较次数少得多
比lg(n!))。排序有4个完全一致的分布
不同的值,并且随着分布变得更加倾斜,samplesort的
等同元素的噱头变得不那么有效,而timsort的适应性
战略找到更多的利用; 在由Kevin Altis提供的数据库中,
排序其高度倾斜“在哪个证券交易所做这家公司
股票交易?“在timsort下快速增长两倍。

然而,尽管timsort在排序上做了许多比较,而且
在几个平台排序运行速度明显慢下
timsort,在其他平台上排序运行速度快得多
timsort。没有其他类型的数据显示出这种野性的X平台行为,
我们没有解释它。我能想到的唯一的事情
这可能会将“应该”高度显着的放缓转变为什么
某些盒子上的高速加速是灾难性的缓存效应
在samplesort中。

但是,timsort“应该”比samplesort慢,因此很难
以为它不是在某些盒子上作为对它的罢工。

+这是基于堆的临时插槽数量的高水位标记(4
每个测试所需的每个字节中的字节),再次带有参数
“15 20 1”:

2 *我排序\排序/排序3排序+排序%排序排序=排序!排序
32768 16384 0 0 6256 0 10821 12288 0 16383
65536 32766 0 0 21652 0 31276 24576 0 32767
131072 65534 0 0 17258 0 58112 49152 0 65535
262144 131072 0 0 35660 0 123561 98304 0 131071
524288 262142 0 0 31302 0 212057 196608 0 262143
1048576 524286 0 0 312438 0 484942 393216 0 524287

讨论:最终要做的(接近)完美平衡的测试
合并(* sort,!sort)需要所有N // 2个临时插槽(或几乎全部)。排序
也最终做了平衡合并,但系统地从中受益很多
稍后在“合并内存”下介绍的初步预合并搜索。
由于随机性,%排序方法在最后具有平衡合并
预期将取代要素的选择会产生无序
元素靠近中点。\ sort,/ sort,= sort是一个简单的一次运行
案件,根本不需要合并。+排序结束了一个非常长的时间
和一个非常短的,从而获得它需要的所有临时空间
MergeState结构体的temparray成员(请注意,这也是
如果新的随机元素改为排序列表的前缀,则为true,
但如果它们出现在“中间”,则不会)。3sort方法N // 3 temp
插槽两次,但在3次随机交换之后剩余的运行长度
显然有很高的差异。

timsort的详细描述如下。

运行

count_run()返回下一次运行中的元素数量。运行也是
“上升”意味着非递减:

a0 <= a1 <= a2 <= ...

或“下降”,这意味着严格递减:

a0> a1> a2> ...

请注意,除非我们从数组开始,否则运行总是至少2个长
最后的元素。

下降的定义是严格的,因为主程序反转
在原地下降跑道,将下坡跑道转变为上升跑道
跑。反转是通过显而易见的快速交换元素完成的
结束,收敛于中间“的方法,如果违反了稳定性
切片包含任何相等的元素。使用严格的定义
降序确保降序运行包含不同的元素。

如果一个数组是随机的,那么我们不太可能会看到长时间运行。如果是自然的
运行包含少于minrun元素(见下一节),主循环
通过稳定的二进制插入排序人为地提升它以减少运行元素
应用于短自然数之后的正确数量的数组元素
跑。在一个随机数组中,* all *运行很可能会像minrun一样长
结果。这有两个主要的好处:

随机数据强烈倾向于完全平衡(两次运行都有
相同的长度)合并,这是最有效的方式进行时
数据是随机的。

2.因为运行永远不会很短,所以其余代码不会生成
英勇的努力来削减每个合并间接费用的几个周期。对于
例如,合理使用函数调用,而不是尝试
内联一切。由于不超过N / minrun运行开始
与每个合并几个“额外”函数调用几乎不可衡量。

计算minrun

如果N <64,minrun为N. IOW,则整体使用二进制插入排序
数组然后; 考虑到尝试一些东西的开销很难打败
票友。

当N是2的幂时,随机数据测试显示minrun的值为
16,32,64和128的工作方式也差不多。数据移动成本为256
在二进制插入排序明显受伤,并在8号增加的数量
的函数调用明显受到伤害。采摘一些 2的力量很重要
在这里,以便合并最终达到完美平衡(见下一节)。我们
在甜蜜的范围内选择32作为一个很好的价值; 在低端选择一个价值
允许自适应噱头更多机会利用更短的自然
运行。

因为sortperf.py只会尝试2的权力,所以需要很长时间才能注意到
这对于一般情况来说不是一个好的选择!考虑N = 2112:

divmod(2112,32)
(66,0)

如果数据是随机排列的,那么我们很可能会以66次运行结束
每个长度为32.这些中的前64个触发完美的序列
均衡合并(参见下一节),留下长度为2048和64的运行
最后合并。自适应噱头可以用少于2048 + 64的比例来实现
比较,但它仍然比必要的更多,并且mergesort的
与samplesort相关的bugaboo - 更多的数据移动(O(N))副本
获得64个元素)。

如果我们在这种情况下采用minrun = 33,那么我们很可能最终会得到64
运行每个长度33,然后所有合并完全平衡。更好!

我们想要避免的是选择minrun,

q,r = divmod(N,minrun)

q是2的幂,r> 0(那么最后的合并只能得到r个元素
并且r

合并模式

为了利用数据中的规律,我们正在合并自然
运行的长度,他们可以变得非常不平衡。这是好事
这种!这意味着我们必须找到一种方法来管理各种各样的
尽管如此,潜在的运行时间可能会不同

稳定性限制了允许的合并模式。例如,如果我们有
连续运行3次

A:10000 B:20000 C:10000

我们不敢先将A与C合并,因为如果A,B和C碰巧包含
一个共同的元素,它会在B中出现的顺序失序
合并必须按(A + B)+ C或A +(B + C)代替。

所以合并总是一次完成两次,并且在原地,
尽管这可能需要一些临时内存(稍后会有更多内容)。

当运行被识别时,其基地址和长度被压入堆栈
在MergeState结构中。然后调用merge_collapse()来查看它是否
应该将它与前面的运行(s)合并。我们希望延迟合并
尽可能长时间地利用后来可能出现的模式,但我们
更喜欢尽快合并来利用这个运行
发现在内存层次结构中仍然很高。我们也不能耽搁合并
“太长”,因为它消耗内存来记住仍然存在的运行
未合并,并且堆栈具有固定大小。

结果是一个很好的妥协保持两个不变式的
堆栈条目,其中A,B和C是三个最大的还没有的长度
合并切片:

A> B + C B> C

请注意,通过归纳,#2意味着等待运行的长度形成a
递减顺序。#1意味着,从右向左读取长度,
待处理的长度至少与斐波纳契数字一样快。
因此堆栈永远不会大于log_base_phi(N)条目的大小,
其中phi =(1 + sqrt(5))/ 21.618。因此,一小堆栈槽就足够了
对于非常大的数组。

如果A <= B + C,则A和C中的较小者与B合并(关系C,对于C而言)
新鲜度缓存原因),并且新运行取代A,B或B,C条目;
例如,如果最后3个条目是

A:30 B:20 C:10

然后B与C合并,离开

答:公元前30年:30

在堆栈上。或者如果他们是

A:500 B:400:C:1000

然后A与B合并,离开

AB:900 C:1000

在堆栈上。

在这两个示例中,合并后的堆栈配置仍然存在冲突
不变#2,并merge_collapse()继续合并运行直到
两个不变量都满足了。作为一个极端的例子,假设我们没有这样做
minrun噱头,自然奔跑的长度分别为128,64,32,16,8,4,2,
和2.直到最后的2被看到,那将不会合并
触发7个完美平衡的合并。

这些规则触发合并时的主旨是平衡运行
长度尽可能接近,同时保持数量上的低限
我们必须记住的运行。这对于随机数据是最有效的,
所有运行可能是(人为强制)长度minrun,和
那么我们会得到一系列完美平衡的合并(也许还有一些合并)
最后的古怪球)。

OTOH,这种类型对于部分有序数据非常有用的原因之一就是要做
具有极大的不平衡运行长度。

合并内存

合并长度A和B的相邻运行非常困难。
已知可以做到的理论构造,但它们太难了
并且实际使用速度慢。但是如果我们的临时记忆等于min(A,B),
这很容易。

如果A较小(函数merge_lo),则将A复制到一个临时数组,将B单独留下,
然后我们可以从temp中执行明显的合并算法
区域和B,开始将商店开到A过去居住的地方。总有一个
原始区域中的自由区域包含许多等于该区域的元素
编号尚未从temp数组合并(在开始时非常正确;
通过归纳进行)。唯一棘手的是如果比较提出了一个
例外,我们必须记住将其余元素从中复制
以避免数组最终有B的重复项。但是
如果我们首先达到B的结尾,那我们就需要做同样的事情,
所以退出代码对于正常和错误情况都是令人愉快的。

如果B较小(函数merge_hi,它是merge_lo的“镜像”),
大致相同,除了我们需要从右向左合并,将B复制到
临时数组,并启动B用于生活的地方右端的商店。

细化:当我们要合并相邻的运行A和B时,我们首先要做的
一种二进制搜索的形式(稍后更多)来看B [0]应该在哪里结束
在A.点之前的A中的元素已经在它们的最后
有效地缩小了A的大小。同样我们也搜索到了
看看A [-1]应该在B中结束的位置,在该点之后B的元素可以
也被忽略。这会削减相同的临时内存量
量。

这些初步搜索可能没有成效,并且可以预期不会
如果数据是随机的,则偿还成本。但他们可以赢得巨大的
时间,复制和内存节省,当他们支付,所以这是其中之一
上面提到的“每合并费用”我们很乐意忍受,因为
最多只有一次很短的时间。这个算法通常是真的
我们愿意赌一把,赢得很多,即使网
对随机数据的期望是负的。

合并算法

merge_lo()和merge_hi()是大部分时间花费的地方。merge_lo
处理A <= B的运行,以及A> B的merge_hi。他们不知道
无论数据是聚类还是统一数据,但是关于合并的可爱之处
是多少种聚类“在多少次”中自我展示“
row获胜的合并元素来自相同的运行。我们只会讨论
merge_lo here; merge_hi是完全相似的。

比较A的第一个元素,通常以明显的方式开始合并
到B的第一个,如果B [0]小于A [0],则将B [0]移动到合并区域,
否则将A [0]移到合并区域。称之为“一次一对”
模式。这里唯一的转折是跟踪连续多少次“
赢家“来自同一场比赛。

如果该计数达到MIN_GALLOP,我们切换到“舞动模式”。这里
我们*搜索B在A [0]所属的位置,然后移动到所有B的位置
它将一个块指向合并区域,然后将A [0]移至合并
区。然后我们搜索A在B [0]所属的位置,同样移动a
在一块大块的A片。然后回到B查找A [0]所属的位置,
等等。我们保持奔跑模式,直到两个搜索都找到要复制的切片
长度小于MIN_GALLOP元素,此时我们回到一对 -
一次性模式。

细化:MergeState结构包含min_gallop的值
控制何时进入舞动模式,初始化为MIN_GALLOP。
merge_lo()和merge_hi()在舞动不付时调高
关闭,然后降低。

舞动

仍然不失一般性,假设A较短。舞动
模式中,我们首先在B中查找A [0]。我们通过“驰骋”来比较
A [0]依次为B [0],B [1],B [3],B [7],…,B [2 ** j-1],…,直到找到
k使得B [2 (k-1)-1]

用断腿舞动

那么为什么我们不总是奔驰?因为它可能会失败,有两个:

1.虽然我们愿意忍受每次比较的小额合并费用
开销是一个不同的故事。每个呼叫另一个功能
比较是昂贵的,gallop_left()和gallop_right()是
为了理智的内联而过于冗长。

2.舞动可以 - 唉 - 需要比线性一次更多的比较
搜索,取决于数据。

#2需要详细信息。如果A [0]属于B [0]之前,舞动需要1
比较确定,与线性搜索相同,除了它花费更多
调用疾驰功能。如果A [0]属于B [1]之前,舞动
需要2比较,再次和线性搜索一样。在第三个比较中,
对B [3]进行舞动检查A [0],如果<=,则需要多一个
比较以确定A [0]是否属于B [2]或B [3]。这是一个总数
4的比较,但如果A [0]确实属于B [2],则线性搜索将具有
发现只有3比较,这是一个巨大的损失!真。它的
需要比较的数量增加33%,并进行比较
昂贵的Python。

在B中的索引#比较线性#驰骋#二进制奔驰
A [0]所属搜索需要比较总数


           0 1 1 0 1

           1 2 2 0 2

           2 3 3 1 4
           3 4 3 1 4

           4 5 4 2 6
           5 6 4 2 6
           6 7 4 2 6
           7 8 4 2 6

           8 9 5 3 8
           9 10 5 3 8
          10 11 5 3 8
          11 12 5 3 8
                                    ...

一般来说,如果A [0]属于B [i],线性搜索需要i + 1比较
以确定,并驰骋总共2 *楼(lg(i))+ 2的比较。
随着我的成长,舞动的优势是无限的,但它不会赢
直到我= 6。在此之前,它会失去两次(在i = 2和i = 4时)和关系
在其他值。在i = 6之后,疾驰总是胜利。

不过,我们不能提前猜测它何时会取胜,所以我们只做一对
直到证据似乎很强烈,这可能会导致疾驰。MIN_GALLOP
是7,这是非常有力的证据。但是,如果数据是随机的,它
简单地会偶尔触发舞动模式,而且
这很有可能是下一个失败的案例之一。另一方面,
在sort的情况下,舞动总是付出,MIN_GALLOP比它大
那么“应该是”。所以MergeState结构保留了一个min_gallop变量
merge_lo和merge_hi调整:我们停留在舞动模式的时间越长,
min_gallop越小越容易转换回
疾驰模式(如果我们将它留在当前的合并中,并且在
下一次合并的开始)。但是,每当疾驰的循环不付款,
min_gallop增加一个,这使得它很难转换回来
以舞动模式(再次在合并和合并中)。对于
随机数据,这一切,但消除了疾驰的惩罚:min_gallop增长
足够大,我们几乎不会进入舞动模式。对于案件
像sort,min_gallop可以降到1。这似乎很好,
但总的来说,这比使用固定的MIN_GALLOP值有一点小改进。

疾驰的并发症

以上描述适用于merge_lo。merge_hi必须合并“
另一端“,并且真的需要从跑步的最后一个元素开始
而不是第一个。从头开始舞动仍然有效,但做得更多
比较它应该(这是显着的 - 我计时双向)。
为此,gallop_left()和gallop_right()函数具有a
“暗示”的论点,这是应该开始舞动的指标。所以
舞步实际上可以从任何指数开始,并以1,3,
7,15,…或-1,-3,-7,-15,…从起始索引开始。

在我输入的代码中,它总是用0或n-1(其中n是)调用
一次运行中的元素数量)。试图做一些更有趣的事情很诱人,
通过某种形式的插值搜索来加速融合; 例如,如果
我们将长度为1的运行与长度为10000的运行合并,索引为5000
可能是最终结果比0或9999更好的猜测。但是
目前还不清楚如何有用地概括这种直觉,以及如何合并
非常不平衡的运行已经取得了出色的表现。

排序是平衡运行可以从更好的方面受益的一个很好的例子
提示值:在可能的范围内,这要使用起始值
偏移量等于acount / bcount的先前值。这样做可以节省
在排序比较的10%。但是,这样做也是一个混杂的包,
伤害其他情况。

比较随机数组上的平均比较数

[注意:这是在新算法使用大约0.1%的比较时完成的
在随机数据上比当前的化身。]

这里list.sort()是samplesort和list.msort()这种排序:

“””
随机导入
从现在的时间进口时钟

def fill(n):
从随机导入随机
在xrange(n)中返回[random()for i]]

def mycmp(x,y):
全球ncmp
ncmp + = 1
返回cmp(x,y)

def timeit(值,方法):
全球ncmp
X =值[:]
bound = getattr(X,方法)
ncmp = 0
t1 = now()
界(mycmp)
t2 = now()
返回t2-t1,ncmp

format =“%5s%9.2f%11d”
f2 =“%5s%9.2f%11.2f”

def drive():
count = sst = sscmp = mst = mscmp = nelts = 0
而真:
n = random.randrange(100000)
尼尔斯+ = n
x = fill(n)

    t,c = timeit(x,'sort')
    sst + = t
    sscmp + = c

    t,c = timeit(x,'msort')
    mst + = t
    mscmp + = c

    计数+ = 1
    如果计数%10:
        继续

    打印“计数”,计数,“nelts”,nelts
    打印格式%(“sort”,sst,sscmp)
    打印格式%(“msort”,mst,mscmp)
    打印f2%(“”,(sst-mst)* 1e2 / mst,(sscmp-mscmp)* 1e2 / mscmp)

驾驶()
“””

我在Windows上运行这个程序,并且一直使用电脑
运行。time.clock()是Windows上的挂钟时间,优于
微秒分辨率。samplesort以1.52%的比较数开始
劣势迅速下降到1.48%,然后在这一小幅内波动
范围。这是我杀死作业之前的最后一部分输出:

数2630尼尔130906543
分类6110.80 1937887573
msort 6002.78 1909389381
1.80 1.49

我们已经以Python的速度在那里完成了将近20亿次的比较,并且
这就够了。

对于大小为2的随机数组(是的,只有2个有趣的数组)
samplesort有50%(!)的比较缺点。这是后果
然后,在最开始的一个上升跑道上取样特殊套管
如果它没有找到升序运行,则回到一般情况
立即。结果是它最终使用两个比较进行排序
[2,1]。令人满意的是,timsort并没有做任何特别的套路,所以必须这样做
教导如何处理上升和下降运行的混合物
有效地在所有情况下。

上一篇:记一次MR报错:Containerisrunningbeyondphysicalmemorylimits,Currentusage...
下一篇:Scala混合组成的类(CLASSCOMPOSITIONWITHMIXINS)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站