Go 言語（以下 Golang）の slice（可変配列）をソートしたいが、slices パッケージのソートが速いらしい。

一般的に、Golang で文字列のスライス（[]string）をソートするには、sort パッケージの sort.Slice や sort.Strings 関数を使うのが簡単です。

ところが、Golang の slices パッケージのソート（golang.org/x/exp/slices.Sort）が速いらしいと聞いて速度比較（ベンチマーク）してみました。

どうやら、クイックソートとヒープソートのマッシュアップであるイントロソートを、さらに改良した Pattern-Defeating Quicksort (PDQsort) の論文をベースに Go で実装したもののようです。

検証環境

$ # OS 情報
$ sw_vers
ProductName:	macOS
ProductVersion:	12.6.2
BuildVersion:	21G320

$ go version
go version 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: [すもも うち もも の も]
}

オンラインで結果をみる @ GoPlayground

slices パッケージは 2023/05 に、golang.org/x/exp の実験用モジュールから標準モジュールに昇格しました!

Go 1.21 から import "slices" で利用できます。

New slices package | Go 1.21 Release Notes @ tip.golang.org

TL; DR _{^{（今北産業）}}

やはり slices.Sort が圧倒的に速く、メモリのリアロケーションもなかったです。

$ benchstat -sort delta results.txt
name                           time/op
_sort_functions/SortSlice-4    60.3ns ± 0%
_sort_functions/SortStrings-4  39.3ns ± 0%
_sort_functions/SlicesSort-4   8.08ns ± 0%

name                           alloc/op
_sort_functions/SortSlice-4     24.0B ± 0%
_sort_functions/SortStrings-4   24.0B ± 0%
_sort_functions/SlicesSort-4    0.00B     

name                           allocs/op
_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

制限と注意時効
- Generics にも対応しているため Go 1.18 以降でしか使えません
- Sort は安定ソートではありません。安定ソートを利用したい（元の並び順が重要な）場合は、less（比較関数）を指定して SortStableFunc を利用します
- ~~exp パッケージ（実験パッケージ）です。つまり、将来的に標準パッケージに昇格したり、廃止（deprecated に）される可能性があります~~。Go 1.21 より標準ライブラリに昇格しました。

TS; 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