详解Go 将在下个版本支持新型排序算法pdqsort
作者:CSDN资讯 时间:2023-10-07 23:49:40
继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");
}
执行结果:
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
来源:https://blog.csdn.net/csdnnews/article/details/124323267
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
一篇文章带你了解kali局域网攻击
![](https://img.aspxhome.com/file/2023/6/107996_0s.jpg)
WEB开发中合理选择图片格式
利用Python在一个文件的头部插入数据的实例
python模拟点击在ios中实现的实例讲解
mysql 5.7.25 安装配置方法图文教程
![](https://img.aspxhome.com/file/2023/1/128371_0s.jpg)
asp网上考试设计思路是怎样的?
php预定义常量
基于Python的自媒体小助手---登录页面的实现代码
![](https://img.aspxhome.com/file/2023/5/109915_0s.png)
深入MYSQL字符数字转换的详解
Python解析pcap文件示例
基于Python实现全自动下载抖音视频
![](https://img.aspxhome.com/file/2023/2/81742_0s.jpg)
微信小程序获取当前位置的详细步骤
![](https://img.aspxhome.com/file/2023/8/136988_0s.jpg)
Python函数的默认参数设计示例详解
Javascript学习第一季 一
TensorFlow低版本代码自动升级为1.0版本
python 实现控制鼠标键盘
Python基础篇之初识Python必看攻略
![](https://img.aspxhome.com/file/2023/4/99604_0s.png)