关于golang:Go语言将引入新型排序算法pdqsort

原文链接:Go语言将引入新型排序算法:pdqsort

哈喽,大家好,我是asong。最近在逛Go仓库时看到了一个commit是对于排序算法的,即pdqsort排序算法,Go打算将在一个版本中反对该排序算法,上面咱们就具体来看一看这个事件;

commit地址:https://github.com/golang/go/…

<img src=”https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/42c63502e8f44a87a904ad340e934d63~tplv-k3u1fbpfcp-zoom-1.image” alt=”截屏2022-05-06 下午1.37.10″ style=”zoom:67%;” />

commit中介绍了pqdsort的测试后果:

  • 在所有基准测试中,pdqsort未体现出比以前的其它算法慢
  • 常见模式中pdqsort通常更快(即在排序切片中快10倍)

pdqsort本质为一种混合排序算法,在不同状况下切换到不同的排序机制,该实现灵感来自C++RUST的实现,是对C++规范库算法introsort的一种改良,其现实状况下的工夫复杂度为 O(n),最坏状况下的工夫复杂度为 O(n* logn),不须要额定的空间。

pdqsort算法的改良在于对常见的状况做了非凡优化,其次要的思维是一直断定目前的序列状况,而后应用不同的形式和门路达到最优解;如果大家想看一下该算法的具体实现,能够查看https://github.com/zhangyunhao116/pdqsort中的实际,其实现就是对上面三种状况的一直循环:

  • 短序列状况:对于长度在 [0, MAX_INSERTION] 的输出,应用 insertion sort (插入排序)来进行排序后间接返回,这里的 MAX_INSERTION 咱们在 Go 语言下的性能测试,选定为 24。
  • 最坏状况,如果发现改良的 quicksort 成果不佳(limit == 0),则后续排序都应用 heap sort 来保障最坏状况工夫复杂度为 O(n*logn)。
  • 失常状况,对于其余输出,应用改良的 quicksort 来排序

具体的源代码实现能够自行查看,本文就不过多剖析了,上面咱们来看一下pdqsort的demo:

import (
    "fmt"

    "github.com/zhangyunhao116/pdqsort"
)

func main() {
    x := []int{3, 1, 2, 4, 5, 9, 8, 7}
    pdqsort.Slice(x)
    fmt.Printf("sort_result = %v\n", x)
    search_result := pdqsort.Search(x, 4)
    fmt.Printf("search_result = %v\n", search_result)
    is_sort := pdqsort.SliceIsSorted(x)
    fmt.Printf("is_sort = %v\n", is_sort)
}

运行后果:

sort_result = [1 2 3 4 5 7 8 9]
search_result = 3
is_sort = true

对于此次排序算法优化你们有什么想法?快快上手体验一下吧~。

参考链接:

  • https://github.com/golang/go/…
  • https://www.easemob.com/news/…
  • https://github.com/zhangyunha…
  • https://arxiv.org/pdf/2106.05…

好啦,本文到这里就完结了,我是asong,咱们下期见。

欢送关注公众号:Golang梦工厂

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据