詳解Go?將在下個版本支持新型排序算法pdqsort

更新時間：2022年04月22日 14:19:01 作者：CSDN資訊

這篇文章主要介紹了Go?將在下個版本支持新型排序算法：pdqsort,而就Go支持pdqsort算法，在HN上引起了不少的討論，有人表示，我們研究排序算法這么久了，很驚訝我們還能想出能產(chǎn)生實際改進的優(yōu)化方案。對此，你怎么看，快快上手體驗一下吧

繼Go 1.18支持泛型后，Go 將在下個版本中支持pdqsort排序算法再次引起了開發(fā)者們的熱切討論。

在這里插入圖片描述

目前，Go倉庫的最新commit中提交了pdqsort的相關功能描述：

在所有基準測試中，pdqsort未表現(xiàn)出比以前的其它算法慢；
在常見模式中，pdqsort通常更快（即在排序切片中快10倍）

那么pdqsort是什么呢？

pdqsort是Pattern-defeating quicksort的縮寫，是一種新型的排序算法，將隨機快速排序的快速平均情況與堆排序的最壞情況快速組合在一起，同時在具有特定模式的輸入上實現(xiàn)了線性時間。 pdqsort是David Mussers introsort的擴展和改進。在zlib許可下，所有代碼都是免費的。

目前在C++和Rust中均有實現(xiàn)，而據(jù)不少開發(fā)者實測發(fā)現(xiàn)，pdqsort較常用的introsort會有較大的性能提升。

C++ 實現(xiàn): https://github.com/orlp/pdqsort
Rust 實現(xiàn): 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");
}

執(zhí)行結(jié)果：

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上引起了不少的討論，有人表示，我們研究排序算法這么久了，很驚訝我們還能想出能產(chǎn)生實際改進的優(yōu)化方案。對此，你怎么看，快快上手體驗一下吧。

參考鏈接：

https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257

https://news.ycombinator.com/item?id=31106157

https://en.cppreference.com/w/cpp/algorithm/sort

到此這篇關于Go 將在下個版本支持新型排序算法pdqsort的文章就介紹到這了,更多相關Go 排序算法pdqsort內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: