はじめまして、しろしゅんと申します。
最初の記事としては若干ニッチなテーマですが、Go 言語におけるソートについて書いてみました！
Go を最近始めた方や日頃からよく書く方を想定しています。
Go 1.21 で slices パッケージが正式に導入され、標準ライブラリでのスライスに対する操作、例えば比較やソート、最大・最小の算出などの機能が拡充されました。
すべての関数でジェネリクスが使用されているため、従来の標準ライブラリに比べ利用者側での書きやすさや拡張性が向上しています。
スライスをソートする関数については、従来の sort パッケージと比べると、大小関係を判定する関数が less func(a, b int) bool から cmp func(a, b E) int に変わったことが大きな変更点と言えるでしょう。
この記事では、新しいソート関数の使用例と、従来ソートに使用されていた less 関数から cmp 関数に変わった経緯などに触れていきます。
func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int)
こちらが追加された slices.SortFunc です。
型パラメーターで少し複雑に見えますが、簡単に言語化すると「任意の型 E のスライス S に対して、2つの E を比較する関数を用いてソートを行う」になります。
関数を呼び出すのに必要な引数は2つあります。1つはソートするスライスそのものです。関数は渡されたスライス自体を操作するため、返り値はありません。
もう1つの引数が比較関数です。こちらは、2つの E の大小関係を自分で定義し、それを示す整数を返す関数です。2つの要素 a b があったとき、a < b ならば負の数、a = b ならば0、a > b ならば正の数を返します。一般的には-1, 0, 1を返します。この大小関係は自分で定義することになります。
例えば、文字列の長さによって比較する場合は以下のようになります。
// https://go.dev/play/p/PGbA7WcOtY9
package main
import (
"fmt"
"slices"
"strings"
)
func main() {
s := []string{"a", "test", ""}
slices.SortFunc(s, func(a, b string) int {
lenA := len(a)
lenB := len(b)
if lenA < lenB {
return -1
} else if lenB < lenA {
return 1
}
return 0
})
fmt.Println(strings.Join(s, ", ")) // , a, test
}
（注: 実際には、比較関数は return cmp.Compare(len(a), len(b)) と一行で書くことができますが、今回は例のために冗長に書いています）
逆順にしたい場合は、元の cmp に対して -1 と 1 を反転させるような cmp を返すユーティリティ関数を書くとわかりやすいです。 以下の例では、a と b を逆にして比較させることで実現しています。
// https://go.dev/play/p/CkZ_956UCSA
package main
import (
"cmp"
"fmt"
"slices"
"strings"
)
var strLenCmp = func(a, b string) int {
return cmp.Compare(len(a), len(b))
}
func toReversedStrings(s []string) []string {
r := slices.Clone(s) // スライスをコピー
slices.SortFunc(r, reverse(strLenCmp))
return r
}
func reverse[E any](cmp func(a, b E) int) func(a, b E) int {
return func(a, b E) int {
return cmp(b, a) // a と b を入れ替えて比較することで逆の結果になる
}
}
func main() {
reversed := toReversedStrings([]string{"a", "test", ""})
fmt.Println(strings.Join(reversed, ", ")) // test, a,
}
less 関数から変わった経緯
sort パッケージでのソート関数 sort.Slice では、引数に less func(a, b int) bool が使用されていました。これはスライスのインデックス a , b に対してそれらの要素が a < b であるかを真偽値で返す関数になります。
slices パッケージのプロポーザルでは、途中まではこれを継承して less func(a, b E) bool を引数として渡す形になっていました12。最終的に cmp func(a, b E) int へ変更された理由は このコメント で言及されています。
The argument in favor of cmp is consistency within package slices. Now if you are sorting a slice and then doing a binary search over it, you only need to write one comparison function and use it in both calls, instead of having to write two different ones.
The primary argument in favor of less is consistency with package sort. This argument doesn't hold up, for two reasons. First, if you are using a slice, you can do everything within package slices; you'll never import sort. Second, and more importantly, the less function signature used by sort is different from the one we were using here. Package sort's less takes indices, while package slices's less takes elements. So you can't use the same function with both packages, and knowing how to write a function for one package does not immediately mean you know how to write one for package slices. So this argument doesn't hold up.
A secondary argument in favor of less is that less functions tend to be shorter than cmp functions. That's true but being able to use the same function with all these different public APIs certainly beats that. If you were really attached to writing less functions you could write a generic converter. (Even so I wouldn't put one in the standard library since it would encourage inefficient code.)
The argument in favor of cmp is much more compelling than either of these, so consider it changed.
拙訳ながら要約しますと
-
slicesパッケージ内での一貫性-
SortFuncでソートした後にBinarySearchFuncでバイナリサーチを行うとき、2つの比較関数を書くより1つの記述で済ませたほうが良い
-
-
sortパッケージとの一貫性は2つの理由で議論が成り立たない- 理由1: スライスを使用する時、
slicesパッケージで完結する - 理由2:
sortとslicesでの比較関数のシグネチャーがそもそも異なり、同じ比較関数を再利用することはできない-
sortではインデックスを引数に取り、slicesでは要素自体を引数に取る - 異なるパッケージ用の関数の書き方を知っているとしても、
slices用の書き方を知っているとはすぐにはならない
-
- 理由1: スライスを使用する時、
-
lessはcmpより短い関数で済む傾向があるが、API で再利用できる関数の方が優れている
sort と slices
スライスの操作に対して同じような関数を提供している2つのパッケージですが、基本的には slices の方を使っていくべきとされています。sort のドキュメントでもそのことが記載されています。
func Slice(x any, less func(i, j int) bool)
Slice sorts the slice x given the provided less function. It panics if x is not a slice.The sort is not guaranteed to be stable: equal elements may be reversed from their original > order. For a stable sort, use SliceStable.
The less function must satisfy the same requirements as the Interface type's Less method.
Note: in many situations, the newer slices.SortFunc function is more ergonomic and runs faster.
ジェネリクスにより比較関数内で直接要素を扱えることや、パフォーマンスが向上していることから、 ほとんどのケースでは slices を使っていくべきでしょう。
一方で、前述の通りソートのための比較関数が less func(a, b int) bool から cmp func(a, b E) int となり、単純な置き換えで移行できないのも事実です。工数をかけて置き換えていくのか、新しい部分から slices を使っていくのかはプロジェクトの方針によって異なるかと思います。
おわりに
シンプルで可読性の高さが売りの Go 言語ですが、Go 1.18 のジェネリクスの導入以降、さらにシンプルに書ける手段が追加され、より書きやすい言語に進化しています。Go 1.23 でのイテレータを始め、今後のメジャーリリースでの新機能に注目ですね。
最後までお読みいただきありがとうございました。