【Golang】比较字符串切片排序速度【2023年上半年版本】

2 年 ago

逸, 科

2 minutes

想要对 Go 语言（以下简称 Golang）的切片（可变数组）进行排序，但是据说 slices 包的排序速度很快。

通常，使用Golang中的sort包中的sort.Slice或sort.Strings函数很容易对字符串切片（[]string）进行排序。

然而，听说Golang的slices包的排序（golang.org/x/exp/slices.Sort）很快，于是我进行了速度比较（基准测试）。

看起来，这似乎是基于 Pattern-Defeating Quicksort (PDQsort) 这篇论文进一步改进的一种结合了快速排序和堆排序的混合排序算法，使用 Go 语言实现的。

验证环境
$ # 操作系统信息
$ sw_vers
产品名称：macOS
产品版本：12.6.2
内建版本：21G320$ go 版本
go 版本 go1.19.5 darwin/amd64

样本：从字符串切片中，按照长度排列，只获取唯一的元素的示例import (
“fmt”

“golang.org/x/exp/slices”
)

func Example() {
list := []string{
“すもも”, “も”, “もも”, “も”, “もも”, “の”, “うち”,
“すもも”, “も”, “もも”, “も”, “もも”, “の”, “うち”,
}

// 按照字典顺序排序
slices.Sort(list)

// 按照长度排序（保持字典顺序）
slices.SortStableFunc(list, func(i, j string) bool {
return len(i) > len(j)
})

// 删除重复元素
reult := slices.CompactFunc(list, func(i, j string) bool {
return i == j
})

fmt.Println(reult)
// Output: [すももうちもものも]
}

slices 包从golang.org/x/exp 的实验模块升级为标准模块，于2023/05发布！从Go 1.21版本开始，可以通过import “slices”进行使用。
新的slices包 | Go 1.21 发布说明 @ tip.golang.org

懶人簡述：（今北產業）

名称分配/操作
_sort_functions/SortSlice-4 24.0B ± 0%
_sort_functions/SortStrings-4 24.0B ± 0%
_sort_functions/SlicesSort-4 0.00B

名称分配次数/操作
_sort_functions/SortSlice-4 1.00 ± 0%
_sort_functions/SortStrings-4 1.00 ± 0%
_sort_functions/SlicesSort-4 0.00

同时使用也很简单。

基本语法
// E 为任意可使用 < <= >= > 进行比较的类型
func slices.Sort[E constraints.Ordered](x []E)
// 示例
func slices.Sort(x []string)

用法示例
import “golang.org/x/exp/slices”

func SortMySlice(input []string) []string {
slices.Sort(input)

return input
}

官方文档：Sort | slices | exp | x | golang.org @ GoDoc

限制和注意事项

由于支持了泛型，因此只能在Go 1.18及更高版本中使用。

Sort不是稳定排序。如果想要使用稳定排序（原始顺序很重要）的话，可以指定less（比较函数）并使用SortStableFunc。

exp包是实验性的包。这意味着将来有可能升级为标准包，也有可能被废弃（deprecated）。

TL;DR（测试源代码）

Gist でソースを見る @ GitHub

func SortSlice(input []string) []string {
	sort.Slice(input, func(i int, j int) bool {
		return input[i] < input[j]
	})

	return input
}

func SortStrings(input []string) []string {
	sort.Strings(input)

	return input
}

func SlicesSort(input []string) []string {
	slices.Sort(input)

	return input
}

// List of functions to be tested
var listFuncs = []struct {
	name string
	fn   func([]string) []string
}{
	{name: "SortSlice", fn: SortSlice},
	{name: "SortStrings", fn: SortStrings},
	{name: "SlicesSort", fn: SlicesSort},
}

package main

import (
	"testing"

	"github.com/hashicorp/go-uuid"
)

// ----------------------------------------------------------------------------
//  Benchmark functions
// ----------------------------------------------------------------------------

func Benchmark_sort_functions(b *testing.B) {
	for _, test := range listFuncs {
		data := getSampleData(b.N)

		b.Run(test.name, func(b *testing.B) {
			b.ResetTimer()

			for i := 0; i < b.N; i++ {
				_ = test.fn(data)
			}
		})
	}
}

// ----------------------------------------------------------------------------
//  Helper functions
// ----------------------------------------------------------------------------

var sampleData = []string{}

func getSampleData(lenData int) []string {
	if len(sampleData) != lenData {
		sampleData = genSampleData(lenData)
	}

	// Create a copy of the sample data since slice is a reference type
	copySlice := make([]string, len(sampleData))
	copy(copySlice, sampleData)

	return copySlice
}

func genSampleData(lenData int) []string {
	tmpData := make([]string, lenData)

	for i := 0; i < lenData; i++ {
		uniqID, err := uuid.GenerateUUID()
		if err != nil {
			panic(err)
		}
		tmpData[i] = uniqID
	}

	return tmpData
}

文献引用

Go1.19に採用されたPattern-defeating Quicksortの紹介 @ m3tech.blog