close

整理 | 夢依丹
出品 | CSDN（ID：CSDNnews）

繼 Go 1.18 支持泛型後，Go 將在下個版本中支持pdqsort排序算法再次引起了開發者們的熱切討論。

目前，Go 倉庫的最新 commit 中介紹了 pdqsort 的相關功能描述：

在所有基準測試中，pdqsort未表現出比以前的其它算法慢；

在常見模式中，pdqsort通常更快（即在排序切片中快10倍）

什麼是 pdqsort 排序算法？

pdqsort 是 Pattern-defeating quicksort 的縮寫，是一種新型的排序算法，將隨機快速排序的快速平均情況與堆排序的最壞情況快速組合在一起，同時在具有特定模式的輸入上實現了線性時間。pdqsort 是 David Mussers introsort 的擴展和改進。在 zlib 許可下，所有代碼都是免費的。

目前在 C++ 和 Rust 中均有實現，而據不少開發者實測發現，pdqsort 較常用的 introsort 會有較大的性能提升。

C++ 實現: https://github.com/orlp/pdqsort

Rust 實現: https://docs.rs/pdqsort/latest/pdqsort/

C++ 代碼 Demo：

#include <algorithm>#include <functional>#include <array>#include <iostream>#include <string_view> int main(){ std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; auto print = [&s](std::string_view const rem) { for (auto a : s) { std::cout << a << ' '; } std::cout << ": " << rem << '\n'; }; std::sort(s.begin(), s.end()); print("sorted with the default operator<"); std::sort(s.begin(), s.end(), std::greater<int>()); print("sorted with the standard library compare function object"); struct { bool operator()(int a, int b) const { return a < b; } } customLess; std::sort(s.begin(), s.end(), customLess); print("sorted with a custom function object"); std::sort(s.begin(), s.end(), [](int a, int b) { return a > b; }); print("sorted with a lambda expression");}

執行結果：

0123456789:sortedwiththedefaultoperator< 9876543210:sortedwiththestandardlibrarycomparefunctionobject 0123456789:sortedwithacustomfunctionobject 9876543210:sortedwithalambdaexpression

Rust 代碼 Demo：

extern crate pdqsort;let mut v = [-5i32, 4, 1, -3, 2];pdqsort::sort(&mut v);assert!(v == [-5, -3, 1, 2, 4]);pdqsort::sort_by(&mut v, |a, b| b.cmp(a));assert!(v == [4, 2, 1, -3, -5]);pdqsort::sort_by_key(&mut v, |k| k.abs());assert!(v==[1,2,-3,4,-5]);

而就 Go 支持 pdqsort 算法，在 HN 上引起了不少的討論，有人表示：我們研究排序算法這麼久了，很驚訝我們還能想出能產生實際改進的優化方案。對此，你怎麼看，快快上手體驗一下吧。

參考鏈接：

https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257

https://news.ycombinator.com/item?id=31106157

https://en.cppreference.com/w/cpp/algorithm/sort

END


本文出自即將上市的《新程序員004》，對話世界級大師，報道中國IT行業創新創造！

— 推薦閱讀 —
☞騰訊被曝要求員工還清90萬房貸再離職；蘋果因不附帶充電器被判賠償消費者7000元；Git 2.6發布|極客頭條
☞《程序員延壽指南》登GitHub熱榜，最多可增壽20年？
☞對話PostgreSQL作者Bruce：「轉行」是為了更好地前行

—點這裡↓↓↓記得關註標星哦~—


一鍵三連 「分享」「點讚」「在看」

成就一億技術人

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 鑽石舞台 的頭像
    鑽石舞台

    鑽石舞台

    鑽石舞台 發表在 痞客邦 留言(0) 人氣()