Go 将在下个版本支持新型排序算法:pdqsort

2022 年 4 月 21 日 CSDN

整理 | 梦依丹       
出品 | 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");}

执行结果:

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 == [12, -34, -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:“转行”是为了更好地前行

点这里↓↓↓记得关注标星哦~ 

一键三连 「分享」「点赞」「在看」

成就一亿技术人

登录查看更多
0

相关内容

专知会员服务
155+阅读 · 2021年3月6日
【经典书】Linux UNIX系统编程手册,1554页pdf
专知会员服务
45+阅读 · 2021年2月20日
专知会员服务
39+阅读 · 2020年9月6日
手写实现李航《统计学习方法》书中全部算法
专知会员服务
48+阅读 · 2020年8月2日
PyTorch 源码解读之即时编译篇
极市平台
0+阅读 · 2022年5月4日
Go 中的泛型:激动人心的突破
InfoQ
0+阅读 · 2022年4月13日
Go中的泛型:激动人心的突破
AI前线
0+阅读 · 2022年4月7日
ONNXRUNTIME C++ 版本推理部署踩坑记录
极市平台
1+阅读 · 2022年3月29日
PyTorch 源码解读之 torch.serialization & torch.hub
极市平台
7+阅读 · 2021年10月27日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2022年6月10日
Arxiv
12+阅读 · 2021年11月1日
Arxiv
11+阅读 · 2019年6月19日
VIP会员
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员