根据去的承诺记录,其计划在下一个版本使用知名快速排序算法——pdqsort。从提交信息来看,这个提交的作者是来自字节跳动的员工,开发者在实施中对pdqsort算法进行了如下的介绍:
<李>在所有基准测试中,pdqsort从未明显慢于以前的算法 <李>在常见模式中,pdqsort通常更快(即在排序切片中快10倍)
pdqsort是Pattern-defeating快速排序的缩写,是一种新型的排序算法,将随机快速排序的快速平均情况与堆排序的最坏情况快速组合在一起,同时在具有特定模式的输入上实现了线性时间.pdqsort是大卫·穆瑟introsort的扩展和改进。
目前该算法有c++和锈版本的实现,据不少开发者实测发现,pdqsort较常用的introsort会有较大的性能提升。
<李> c++实现:https://github.com/orlp/pdqsort <李>锈实现:https://docs.rs/pdqsort/latest/pdqsort/
0 留言