性能文章>Go 将在下个版本引入快速排序算法 pdqsort>

Go 将在下个版本引入快速排序算法 pdqsort原创

https://a.perfma.net/img/3110416
2年前
282002

根据 Go 的 commit 记录,其计划在下一个版本使用知名快速排序算法——pdqsort。从提交信息来看,这个 commit 的作者是来自字节跳动的员工,开发者在 commit 中对 pdqsort 算法进行了如下的介绍:

  • 在所有基准测试中,pdqsort 从未明显慢于以前的算法
  • 在常见模式中,pdqsort 通常更快(即在排序切片中快 10 倍)

pdqsort 是 Pattern-defeating quicksort 的缩写,是一种新型的排序算法,将随机快速排序的快速平均情况与堆排序的最坏情况快速组合在一起,同时在具有特定模式的输入上实现了线性时间。pdqsort 是 David Mussers introsort 的扩展和改进。

目前该算法有 C++ 和 Rust 版本的实现,据不少开发者实测发现,pdqsort 较常用的 introsort 会有较大的性能提升。

点赞收藏
堆堆

【HeapDump性能社区官方小编】各位堆友们,+微信号perfMa,可以联系上堆堆哦~

请先登录,感受更多精彩内容
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步
2
0
https://a.perfma.net/img/3110416
堆堆

徽章

【HeapDump性能社区官方小编】各位堆友们,+微信号perfMa,可以联系上堆堆哦~