Overview
Go1.23 で range-over func を取り込んだ slices package 内の SortedFunc と SortedStableFunc の挙動について少し調べました。
Sort における Stable とは？
Godoc を読んでも完全には理解できなかったので ChatGPT に聞いてみました。
ソートにおける「stable（安定）」とは、ソートされた後も、元の順序が保持される性質を指します。
具体的には、ソートする際に、同じ値を持つ要素が複数ある場合、それらの要素の相対的な順序がソート後も変わらないことを意味します。例えば、リストの中に同じ値を持つ要素AとBがあり、ソート前にAがBの前にあったとします。安定なソートを行った場合、ソート後もAはBの前に残ります。
例:
以下に、安定なソートと不安定なソートの違いを示します。
ソート前
[(3, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
安定なソート後 (数値でソート)
[(1, 'b'), (2, 'c'), (3, 'a'), (3, 'd')]
この例では、3の値を持つ2つの要素 (3, 'a') と (3, 'd') の相対的な順序は、ソート前と後で変わっていません。
不安定なソート後 (数値でソート)
[(1, 'b'), (2, 'c'), (3, 'd'), (3, 'a')]
不安定なソートでは、3の値を持つ要素の相対的な順序がソート前後で変わってしまっています。
安定なソートは、特に複数のキーでソートする際に重要です。たとえば、最初に名前でソートし、その後年齢でソートする場合、安定なソートを使用することで、同じ年齢の人々の名前の順序が保たれます。
Sort するときに元の並び順を保証したいケースがあり、この保証をしてくれるメソッドが SortedStableFunc になります。
実際に動かしてみた
上記の説明のとおりなので期待するふるまいは以下になります。
- SortedFunc
- Sort した結果、同じ値の要素があったときの、その同じ要素同士の並び順は保証されない。
- SortedStableFunc
- Sort した結果、同じ値の要素があったときに、元の配列の並び順の通りに Sort される（並び順が保証される)
package main
import (
"fmt"
"slices"
)
type taple struct {
a int
b string
}
func main() {
taples1 := []taple{{3, "dd"}, {1, "a"}, {3, "cc"}, {3, "ff"}, {2, "b"}, {4, "ee"}}
s1 := slices.SortedFunc(slices.Values(taples1), func(a, b taple) int {
return a.a - b.a
})
fmt.Println(s1)
taples2 := []taple{{3, "dd"}, {1, "a"}, {3, "cc"}, {3, "ff"}, {2, "b"}, {4, "ee"}}
s2 := slices.SortedStableFunc(slices.Values(taples2), func(a, b taple) int {
return a.a - b.a
})
fmt.Println(s2)
}
ref: https://go.dev/play/p/ePGk-95Z8EW
結果なんですが、 SortedFunc でも並び順が何故か固定化されました（なぜ...).
上記の Playground で実行してみると SortedFunc の結果と SortedStableFunc の結果は何度実行しても同じ結果になりました。
ただ、利用するときには元の配列の並び順を保証してくれるのは SortedStableFunc なので、ユースケースに応じて使い分けるのが良さそうです。
調べたときの PR
github.com
