Goで「あれ?順番が思った通りじゃない...?」となったときに読むページ

本記事は Go Advent Calendar 2022 の19日目の記事です。

Goで開発していると「あれ？思った通りの順番で出力してくれない...」という場面に出くわすことがあると思います。

それぞれの事象について、じっくりと処理を追っていけば原因を特定することはできますが、 事前に はまりポイント を知っておけば未然に防げます。

この記事では、筆者が遭遇したそんなはまりポイントについて共有していきます。

他にも「こういうパターンがあるよ！」という方がいらっしゃいましたら、コメント欄に是非ご記載ください！

sliceのスコープを意識せずにソートする

Goの標準パッケージ sort には、sliceをソートするときに便利なメソッドが揃っており、以下のように要素の型によらず呼ぶことができます。

a := []int{3, 1, 2}
sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
fmt.Println(a)
// => [1 2 3]

sliceのスコープがソートを行ったスコープに閉じている場合は、特に意識せず上記のようにメソッド sort.Slice() を用いれば簡単にソートできるのですが、複数のスコープにまたがっている場合は注意が必要です。

例えば次のようなコードを考えてみましょう。

type Ranking []struct {
	UserName string
	Score    int64
}

func (r Ranking) PrintUsers() {
	for _, v := range r {
		fmt.Println(v.UserName)
	}
}

func (r Ranking) PrintRanking() {
	sort.Slice(r, func(i, j int) bool { return r[i].Score >= r[j].Score })
	for i, v := range r {
		fmt.Println(i+1, v.UserName, v.Score)
	}
}

func main() {
	// ユーザー名で昇順にソートされている
	ranking := Ranking{
		{"Alice", 600},
		{"Asuna", 500},
		{"Kirito", 700},
	}

	// ...
}

データベースからとってきたランキングデータを使って、ユーザー一覧を出力するメソッド Ranking.PrintUsers() と、スコアが高い順（降順）でランキングを出力するメソッド Ranking.PrintRanking() を定義します。ランキングデータはユーザー名で昇順にソートされていることに気をつけてください。

ここで、ランキングデータを取得した段階で PrintUsers() を呼ぶと、ユーザー名で昇順ソートされた状態で出力されるかと思います。これは特に問題ありませんね。

しかし、PrintRanking() でランキングを出力した後に、ユーザー名で昇順になっていることを期待して PrintUsers() を呼んでも、期待とは裏腹に順番が変わっていることに気づきます。

ranking.PrintUsers()	
// Alice
// Asuna
// Kirito
	
ranking.PrintRanking()
// 1 Kirito 700
// 2 Alice 600
// 3 Asuna 500
	
ranking.PrintUsers()
// Kirito
// Alice
// Asuna
// ↑最初と並び順が違う

Playground

これは PrintRanking() の中でランキングをソートした状態が残っているために起こるのです。

上記の例は比較的簡単だったため、すぐに原因に気づくことができました。

ただ、気づきにくい例として、マスターデータを取得後に、そのデータを利用する箇所でソートを行ってしまったがゆえに、別の箇所でそのマスターデータを利用するときに順番が変わっていることがあります。

また他の例として、標準パッケージ text/template を使ってテンプレートから並行処理で自動生成を行う際に、テンプレート中でソート処理がある「メソッドや template.FuncMap で定義した関数」を呼んでしまい、処理するたびにsliceの内容が変わっていることがあります。

これに対処するやり方として、①メインの処理を行う前にソートしておく、②ソートをする直前で元のsliceをコピーしてコピー先のsliceをソートして使う、という2点がありますが、個人的にはできるならパフォーマンス的にも前者をオススメしておきます。

通常のソートと安定ソートを使い分けていない

世の中には2種類のソートがあります。安定しているかそれ以外かです。

Goのメソッド sort.Slice() は安定していないソートです。

安定していないとはどういうことかと言うと、sliceから任意の2つの要素を取ったときに比較結果が同等であった場合は元の順番を保ったままソートしてほしいが、そうならないソートのことを指します。

少し小難しい話になってきました。例を示しましょう。

type Ranking []struct {
	UserName  string
	ClearTime time.Duration
}

func (r Ranking) PrintRanking() {
	for i, v := range r {
		fmt.Println(i+1, v.UserName, v.ClearTime)
	}
}

func main() {
	// ユーザー名で昇順にソートされている
	ranking := Ranking{
		{"Alice", time.Second * 1},
		{"Asuna", time.Second * 2},
		{"Kirito", time.Second * 1},
	}

	sort.Slice(ranking, func(i, j int) bool { return ranking[i].ClearTime < ranking[j].ClearTime })

	ranking.PrintRanking()
}

Playground

先ほどの例と似ていますが、スコアではなくクリアタイムになっていて、タイムの早い順（昇順）でソートしてからランキングを表示しようとしています。

このソートでは Alice と Kirito のタイムが同じなので、元の Alice, Kirito という順番を保ったまま以下のように出力されることを期待されるかもしれません。

1 Alice 1s
2 Kirito 1s
3 Asuna 2s

ただソートのアルゴリズムによっては、タイムが同じでも Kirito と Alice の順番が入れ替わって出力されるかもしれません。

1 Kirito 1s
2 Alice 1s
3 Asuna 2s

そんなときは、安定ソートを使いましょう。幸いなことに Go にも安定ソートであるメソッド sort.SliceStable() が用意されています！

slice の要素が数値や文字列などのプリミティブ型（Goでは Basic Types と呼ばれています）であったり、パフォーマンスを重視する場合は sort.Slice() を使っても良いかもしれませんが、それ以外のときは細心の注意を払って使用しましょう。

ちなみに sort.Slice() の内部実装は pdqsort と呼ばれる比較的最近になって発表された論文に基づいたアルゴリズムになっていて、要素数が少ないときは（Go1.19.4時点では12）安定ソートを用いるようになっているので、初めから要素が少ないと分かっている場合は安心して使えます。

mapをsliceに変換したままにする

重複する要素を持つ slice から重複を取り除いた slice を作るとき、map を用いて行うことが多いかと思います。
そのとき、以下のような関数 uniq() を実装していませんでしょうか？

func uniq(input []int) []int {
	h := make(map[int]struct{})
	for _, v := range input {
		h[v] = struct{}{}
	}

	result := make([]int, 0)
	for k, _ := range h {
		result = append(result, k)
	}

	return result
}

func main() {
	a := []int{1, 1, 2, 3, 4, 4, 4, 5, 5, 6, 7, 7, 7, 7, 8, 8, 9}
	fmt.Println(uniq(a))
	// => [1 2 3 4 5 6 7 8 9] ?
}

Playground

目的自体は果たしているので、このコードでなんら問題はありません。

ただ、map から range で値を取り出す際に毎回ランダムで値が取り出されるため、uniq() を呼び出すたびに引数が同じでも結果が異なります（Playground でも珍しく毎回実行結果が異なる）。

uniq() の末尾で result をソートしてあげたほうがより親切と言えるでしょう。

---

話は逸れますが、map の内部処理に少し触れてみます。

map は内部のあらゆるところで乱数を用いています。Go の初期の実装では乱数は用いられていなかったのですが、map から要素を取り出す際の順序が固定されていることに依存した処理を書かせないために乱数が用いられるようになりました。この辺りの議論は以下の issue にて行われています。

https://github.com/golang/go/issues/6719

map の内部処理で乱数が用いられている箇所は Go1.19.4 時点では次の3箇所で確認できました。なお Go の map はデータ構造でいうところの Hashmap で実装されているのですが、ハッシュやバケットなどの専門用語の解説は本筋ではないため他に譲ります。

• ハッシュ計算
• range で map を走査するときのバケットの開始位置
• バケットの容量がいっぱいになってきているか測るとき

また、ハッシュ計算に用いられる乱数はハッシュ計算のたびに初期化されるのではなく、要素数が 0 になる以下のタイミングで初期化されます。

• map が新規作成されたとき
• delete で要素数が 0 になったとき
• clear されたとき

map の内部実装に関する詳しい解説は、GoCon 2018 Spring で来日され登壇された Dave さんの How the Go runtime implements maps efficiently (without generics) が詳しいです。

最後に

本記事では、開発中に遭遇する意図せず順番が変わるパターンについて、

• sliceのスコープを意識せずにソートする
• 通常のソートと安定ソートを使い分けていない
• mapをsliceに変換したままにする

の3つを紹介しました。
ほかにも色んなパターンがあると思うので、ぜひコメント欄に記載お願いします！