Go 将在下个版本支持新型排序算法：pdqsort-轻识

点击上方蓝色“polarisxu”关注我，设个星标，不会让你失望

整理 | 梦依丹

出品 | 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 #include #include #include #include  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");}

执行结果：

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator< 9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object 0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object 9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

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

往期推荐

观点：泛型会让你的 Go 代码运行变慢？

我是 polarisxu，北大硕士毕业，曾在 360 等知名互联网公司工作，10多年技术研发与架构经验！2012 年接触 Go 语言并创建了 Go 语言中文网！著有《Go语言编程之旅》、开源图书《Go语言标准库》等。

坚持输出技术（包括 Go、Rust 等技术）、职场心得和创业感悟！欢迎关注「polarisxu」一起成长！也欢迎加我微信好友交流：gopherstudio