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 パッケージ（実験パッケージ）です。つまり、将来的に標準パッケージに昇格したり、廃止（。Go 1.21 より標準ライブラリに昇格しました。deprecatedに）される可能性があります
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