引用nightcracker · 2021-07
“I've long since implemented that in pdqsort [2], along with other techniques described by me in [3]”
说自己早已在 pdqsort 中实现了该技术
对已排序、重复元素多等输入自适应提速的混合快速排序
论文提出一种不需要三路比较的荷兰国旗问题新解法,使含 k 个不同元素的输入有 O(nk) 的最坏情况运行时间。结合其他已知与新的技术,构成一种混合排序(pdqsort),它不会显著慢于普通快速排序,而在许多输入分布上大幅加速。
评论者把 pdqsort 当作比标准库 std::sort 更快的常用替代实现来提,并强调它对已排序和有规律输入的适应性。
只有一篇候选与目标直接相关:BlockQuicksort 解决分支预测失败,pdqsort 在其基础上扩展,所以先读它。
pdqsort 的划分步骤借用了它的分块缓冲思想,以减少分支预测失败。
读分块比较并缓冲结果的划分方法,以及为何能避免分支预测失败。
目标论文:在快速排序上加入荷兰国旗新解法等技术,适应各种输入分布。
读重复元素的划分、对已排序和模式输入的检测,以及最坏情况回退到堆排序。
“I've long since implemented that in pdqsort [2], along with other techniques described by me in [3]”
“pdqsort (for pattern-defeating quicksort) Pattern-defeating Quicksort is also popular.”
“pdqsort paper: Pattern-defeating Quicksort”