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() {
    // sort の種類を設定してみる
    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

emahiro/b.log

日々の勉強の記録とか育児の記録とか。

slices.SortedFunc の挙動を少し調べて疑問に思った話