详解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
猜你喜欢
- 注释:在大多数的情况下,修改MySQL是需要有mysql里的root权限的,所以一般用户无法更改密码,除非请求管理员。方法1使用phpmya
- 为什么是三谈为什么是三谈呢?一是因为这真的是一个被说烂的话题,二是因为太师傅在n年前就写过这篇再谈iframe自适应高度。之所以再提该问题,
- 今天遇到这个问题,上网查到以下解决方法:1.检查你的磁盘剩余空间是否足够,如果没有磁盘剩余空间,则清理磁盘,腾出空间
- 讨论Web开发技术的历史,当然要先说说Web的起源。众所周知,Web这个Internet上最热门的应用架构是由Tim Berners-Lee
- 如何在Typescript中使用for...in ?本人在TS中用for...in出现了些问题,也想到了一些解决方法。那么先来看看下面报错的
- 使用MySQL,安全问题不能不注意。以下是MySQL提示的23个注意事项:1、如果客户端和服务器端的连接需要跨越并通过不可信任的网络,那么就
- 网页布局中常有的一种情况就是网页主体部分分成一行两列;而在很多种情况下,设计师们常把左右两列的背景色设计成不同色彩,以实现内容块的明显区分;
- 介绍分面是指事物的多维度属性。例如一本书包含主题、作者、年代等分面。而分面搜索是指通过事物的这些属性不断筛选、过滤搜索结果的方法。可以将分面
- 一、前言在学习深度学习会发现都比较爱用python这个argparse,虽然基本能理解,但没有仔细自己动手去写,因此这里写下来作为自己本人的
- 任何数据库系统都无法避免崩溃的状况,即使你使用了Clustered,双机热备等等,仍然无法完全根除系统中的单点故障,何况对于大部分用户来说,
- 高效的css写法中的一条就是使用简写。通过简写可以让你的CSS文件更小,更易读。而了解CSS属性简写也是前端开发工程师的基本功之一。今天我们
- 本文实例讲述了php中正则替换函数ereg_replace用法。分享给大家供大家参考。具体如下:下面的实例是利用php 正则替换函数 ere
- 本文实例讲述了PHP实现的DES加密解密类定义与用法。分享给大家供大家参考,具体如下:今天写App接口的时候需要传递加密数据给APP端,于是
- 本文重在实践和测试,如果你还不了解Data URI,推荐先阅读秦歌的Data URI 和 MHTML。旺旺点灯(JS)实践经过:因为要对SR
- PHP fprintf() 函数实例把一些文本写入到名为 "test.txt" 的文本文件:<?php $numb
- Dreamweaver快捷键大全,记住一些常用的快捷键会大大提高你的网页设计效率,如果你都使用快捷键,那么如果你去面试工作就容易被录取,呵呵
- 可以通过 reflect.DeepEqual 比较两个 slice/struct/map 是否相等:package main import
- 如何显示存储在BLOB字段中的图像?showimges.asp' 在浏览器上单独显示图像 <%@ 
- 在做DHTML时,我们在某些情况下要用setAttribute(attri, value)方法定义元素的attribute。同时与getAt
- EF Core 是一个ORM(对象关系映射),它使 .NET 开发人员可以使用 .NET对象操作数据库,避免了像ADO.NET访问数据库的代