Go 將引入快速排序算法 pdqsort
互聯網 2022/5/2 14:12:45
| 根據 Go 的 commit 記錄，其計劃在下一個版本使用知名快速排序算法——pdqsort。 |
從提交信息來看，這個 commit 的作者是來自字節跳動的員工，開發者在 commit 中對 pdqsort 算法進行了如下的介紹：
在所有基準測試中，pdqsort 從未明顯慢于以前的算法
在常見模式中，pdqsort 通常更快（即在排序切片中快 10 倍）
pdqsort 是 Pattern-defeating quicksort 的縮寫，是一種新型的排序算法，將隨機快速排序的快速平均情況與堆排序的最壞情況快速組合在一起，同時在具有特定模式的輸入上實現了線性時間。pdqsort 是 David Mussers introsort 的擴展和改進。
目前該算法有 C++ 和 Rust 版本的實現，據不少開發者實測發現，pdqsort 較常用的 introsort 會有較大的性能提升。
C++ 實現: https://github.com/orlp/pdqsort
Rust 實現: https://docs.rs/pdqsort/latest/pdqsort/
關于找一找教程網
本站文章僅代表作者觀點，不代表本站立場，所有文章非營利性免費分享。
本站提供了軟件編程、網站開發技術、服務器運維、人工智能等等IT技術文章，希望廣大程序員努力學習，讓我們用科技改變世界。
[Go 將引入快速排序算法 pdqsort]http://www.yachtsalesaustralia.com/tech/detail-318737.html
- 2022-05-19常見排序算法的golang 實現
- 2022-05-19[LeetCode] 1534. Count Good Triplets
- 2022-05-19django_模型層補充
- 2022-05-19django里的orm操作
- 2022-05-19django(6)
- 2022-05-19django框架7
- 2022-05-18Golang第五章：結構體和對象
- 2022-05-18fjango7
- 2022-05-18golang 的net包的網絡編程 TCP | HTTP | RPC
- 2022-05-18Go基礎3：函數、結構體、方法、接口
