【Golang】slices.Sort 文字列スライスのソート速度比較【2023 年上半期版】

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

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

ところが、**Golang の `slices` パッケージのソート（<code><a href="https://pkg.go.dev/golang.org/x/exp/slices#Sort" target="_blank">golang.org/x/exp/slices.Sort</a></code>）が速い**らしいと聞いて速度比較（ベンチマーク）してみました。

どうやら、[クイックソート](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)と[ヒープソート](https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88)のマッシュアップである[イントロソート](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%B3%E3%83%88%E3%83%AD%E3%82%BD%E3%83%BC%E3%83%88)を、さらに改良した [Pattern-Defeating Quicksort (PDQsort) の論文](https://arxiv.org/pdf/2106.05123.pdf)をベースに [Go で実装したもの](https://cs.opensource.google/go/x/exp/+/master:slices/zsortordered.go;l=58;drc=a68e582fa157abff310e2a9a287b21a1fe1e1629)のようです。

<details><summary>検証環境</summary>

```shell-session
$ # OS 情報
$ sw_vers
ProductName:	macOS
ProductVersion:	12.6.2
BuildVersion:	21G320

$ go version
go version go1.19.5 darwin/amd64
``` 

</details>

<details><summary>サンプル：文字列スライスから、ユニークな要素だけを文字列の長い順に取り出す例</summary>

```go:一意のスライスを長い順に
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: [すもも うち もも の も]
}
```

- [オンラインで結果をみる](https://go.dev/play/p/6DnAg9Gs4kH) @ GoPlayground

</details>

:::note info
`slices` パッケージは 2023/05 に、`golang.org/x/exp` の実験用モジュールから標準モジュールに[昇格しました](https://cs.opensource.google/go/go/+/0df681248862a34ff1233cdc4cf0b036e4761652)!

Go 1.21 から [`import "slices"` で利用できます](https://cs.opensource.google/go/go/+/master:src/slices/example_test.go)。

- [New slices package](https://tip.golang.org/doc/go1.21#slices) | Go 1.21 Release Notes @ tip.golang.org

:::


## TL; DR <sub><sup>（今北産業）</sup></sub>

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

    ```shell-session
    $ 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   
    ```
2. 使い方も簡単。

    ```go:基本構文
    // E は < <= >= > で比較可能な任意の型
    func slices.Sort[E constraints.Ordered](x []E)
    // 例
    func slices.Sort(x []string)
    ```
    
    ```go:使用例
    import "golang.org/x/exp/slices"
    
    func SortMySlice(input []string) []string {
    	slices.Sort(input)
    
    	return input
    }
    ```
    - 公式ドキュメント: [Sort](https://pkg.go.dev/golang.org/x/exp/slices#Sort) | slices | exp | x | golang.org @ GoDoc

3. 制限と注意時効

    - Generics にも対応しているため Go 1.18 以降でしか使えません
    - [Sort](https://pkg.go.dev/golang.org/x/exp/slices#Sort) は[安定ソート](https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E3%82%BD%E3%83%BC%E3%83%88)ではありません。安定ソートを利用したい（元の並び順が重要な）場合は、`less`（比較関数）を指定して [SortStableFunc](https://pkg.go.dev/golang.org/x/exp/slices#SortStableFunc) を利用します
    - ~~[exp パッケージ](https://cs.opensource.google/go/x/exp)（実験パッケージ）です。つまり、将来的に標準パッケージに昇格したり、廃止（`deprecated` に）される可能性があります~~。Go 1.21 より標準ライブラリに昇格しました。

## TS; DR <sub><sup>（テストのソース）</sup></sub>

- [Gist でソースを見る](https://gist.github.com/KEINOS/6ac1c26003ab362c4d625b7a3a9b3dab) @ GitHub

```go:テストされる関数
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},
}
```

```go:ベンチマーク
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の紹介](https://www.m3tech.blog/entry/pdqsort) @ m3tech.blog