Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1672812
  • 博文数量: 1279
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 13084
  • 用 户 组: 普通用户
  • 注册时间: 2018-03-07 16:26
个人简介

Linux学习小标兵,专注Linux资讯分享,技术文章分享

文章分类

全部博文(1279)

文章存档

2023年(236)

2022年(285)

2021年(265)

2020年(248)

2019年(213)

2018年(32)

我的朋友

分类: LINUX

2022-05-02 23:40:56

导读 根据 Go 的 commit 记录,其计划在下一个版本使用知名快速排序算法——pdqsort。

从提交信息来看,这个 commit 的作者是来自字节跳动的员工,开发者在 commit 中对 pdqsort 算法进行了如下的介绍:

在所有基准测试中,pdqsort 从未明显慢于以前的算法

在常见模式中,pdqsort 通常更快(即在排序切片中快 10 倍)

Go 将引入快速排序算法 pdqsortGo 将引入快速排序算法 pdqsort

pdqsort 是 Pattern-defeating quicksort 的缩写,是一种新型的排序算法,将随机快速排序的快速平均情况与堆排序的最坏情况快速组合在一起,同时在具有特定模式的输入上实现了线性时间。pdqsort 是 David Mussers introsort 的扩展和改进。

目前该算法有 C++ 和 Rust 版本的实现,据不少开发者实测发现,pdqsort 较常用的 introsort 会有较大的性能提升。

C++ 实现:

Rust 实现:


本文来自《Linux就该这么学》官方资讯站。
阅读(230) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~