-
Notifications
You must be signed in to change notification settings - Fork 0
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
std::sort 的流程分析 #11776
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
std::sort 的流程分析
https://ift.tt/eQF7wiI
摘要
本文深入探索
g++
钦定的西半球最快的排序算法说明
下文中提到的 STL 都是指 GNU ISO C++ Library(即
libstdc++
)下的具体实现流程分析 1-policy
STL 的 sort 实现是使用一种内省式排序的算法,也就是大范围(使用快排 + 递归过深使用堆排)+ 最终使用完整的插入排序来完成
流程分析 2-插入排序
出于可读性的考虑,首先看
__final_insertion_sort
STL 实现的插入排序是带有优化的,它把区间分为两部分
[first, first + _S_threshold)
,进行完整的插入排序(里面的技巧后面会提)[first + _S_threshold, last)
,进行不含边界检查的插入排序下面展式这两种插入排序的微妙区别
完整的插入排序
unguarded 的插入排序
__insertion_sort
相对于教科书级别的实现,只多了一步##flag #0
处的预先判断*i < *first
,常规的实现是从
i
一直往前直到first
逐个判断是否需要swap
来实现插入,但是STL
这里的预判如果为true
,则直接可以移动整个[first, i]
区间往后偏移一位,减少i-first+1
次判断如果为
false
就是常规的线性遍历__unguarded_linear_insert
,这里虽然保证了*first < *i
,但是[first+1, i)
与i
是否有序还是需要接着判断的,之所以使用unguarded
是因为first
必然是[first, i)
区间最小的值,while (__comp(__val, __next))
必不满足,因此不需要每次确认__last != __first
,同样是减少了i-first+1
次判断成本,另外,__val
是固定不变的,而不是每次都取迭代器上的值,可以说是连一点访问成本都抠下来了问题出现在
__unguarded_insertion_sort
,内部是直接从first
到last
(的开区间)都调用__unguarded_linear_insert
,从前面的分析可以看出,使用__unguarded_linear_insert
要求在first
前面(不包含first
)要有一个比[first,last)
都小的值才能保证安全(因为它根本没有边界保护),回到__final_insertion_sort
的##flag #1
处,也就是要求[__first, __first + _S_threshold)
中必然存在整个区间[first, last)
的最小值,我们必须回去分析__introsort_loop
的流程来获得答案流程分析 3-轴点划分
__introsort_loop
的流程如下(所以说每个函数都标注
This is a helper function
有啥意义,又没说是干嘛的)首先分析
__depth_limit
,这是一个限制递归深度的参数,由于快排存在间歇性拉垮的性能表现,有必要在超过一定阈值限制后把它转为另一种排序算法来避免最坏情况在
__sort
的##flag #2
可以看到它的玄学参数为std::__lg(__last - __first) * 2
,从结论上来说,就是限制快排的递归深度为 \(2 \cdot log_2(last - first)\)别问
std::__lg
是怎么实现的,我也没看懂(upd. 看懂了,留意返回值类型,是下取整)接着了解
__unguarded_partition_pivot
,从上面的代码形式和命名就可以得知是一个返回轴点的划分算法它的划分值挑选挺简单粗暴的,就是挑选
first+1, mid, last-1
三个数的中值,然后std::swap
到first
位置上去,所以说关键就是最后一行的__unguarded_partition
整个流程是非常教科书的,把大于等于
piviot
的first
和小于等于pivot
的last
进行交换并逼近中间,直到两个迭代器交错或相等,从结果上来说,就是保证[first, return_iter)
的任意迭代器iter
都满足*iter<=*pivot
,这里返回的位置return_iter
并不严格等于*__pivot
,因为这样可以减少一次std::swap(*__pivot, *__first)
的成本流程分析 4-堆排序
当
__depth_limit == 0
时,__introsort_loop
是调用__partial_sort
,这个过程实际就是堆排序这一部分并不打算接着分析下去
流程分析 5-内省式排序
再次贴上内省式排序的框架
我们已经分析了上述所有细节,重新来看整体的流程
__introsort_loop
只处理区间大小大于_S_threshold
的子区间,否则直接忽略,因此它不具有完整排序的功能__depth_limit
下限,将会强行使用堆排来结束流程,此时排序的区间是确保有序的__introsort_loop
使用##flag #4
处的__last = __cut
来替代掉尾递归__introsort_loop(__first, __cut, __depth_limit, __comp)
,可能对不聪明的编译器有优化效果那么重新回到
__unguarded_insertion_sort
的问题在
__sort
的流程中,__introsort_loop
完成后接着就是__final_insertion_sort
,先是对前_S_threshold
个元素进行完整的插入排序,剩下的绝大部分是不受保护的__unguarded_insertion_sort
,这里要求[__first, __first + _S_threshold)
满足一个隐含的要求:[__first, __last)
的最小值必须落在里面那么
__introsort_loop
是怎么做到的?似乎我前面的分析完全没有提及这个问题,确实需要推理,而不是流程上的讲解在调用
__unguarded_insertion_sort
之前,区间的情况有多种可能_S_threshold
的大小,直接跳过了introsort
introsort
,但是没有达到depth_limit
下限就结束了introsort
,到达depth_limit
下限强制结束了在这里我们考虑
[first, last)
区间的最左端,因为introsort
肯定会划分出一个最左边的轴点pivot
(或者叫 cut),那么这个范围就是[first, pivot)
对于情况一,不足大小限制,在插入排序流程中并不会进行
__unguarded_insertion_sort
,而是完整的插入排序流程,因此是安全的对于情况二,没有到达下限就结束,意味着
pivot
落在(first, first + _S_threshold]
,由划分算法的性质可知,[first, pivot)
肯定小于等于(pivot, last)
,间接实现了最小值落在[__first, __first + _S_threshold)
区间的需求对于情况三,能进入该分支意味着
pivot
在depth_limit
次机会中都没有落到(first, first + _S_threshold]
里面,因此切换为堆排,按照堆排的特性,最左端的区间的最小值必然落在first
这个位置,而这个最左端区间是划分算法得来的,因此最左端肯定是整个[first, last)
区间的最小值也就是说,
introsort
是隐式地维护了这一条性质:最小值必然落在[__first, __first + _S_threshold)
区间,从而保证后面的__unguarded_insertion_sort
流程是安全的THE END
完整的分析可以见我的 github: Caturra000/RTFSC
虽然解释都是一样的啦
via Caturra’s Blog
September 10, 2024 at 11:06AM
The text was updated successfully, but these errors were encountered: