技術トークでドヤるために Go の select を深ぼってみた
はじめに
先日の記事で Go の select についての問題を出題しました。
【Go 腕試し】複数チャネルの select
この記事はその深掘り解説みたいなものです。
Go のランタイムが実装されているruntime/select.go のコードを読み解き、select が準備万端な ch をどのように ランダム選択 しているかを解説します。
select のランダム選択を簡単におさらい
以下のコードでは、ch1 と ch2 の両方が送信済みで、どちらも受信可能な状態です。
package main
import "fmt"
func main() {
ch1 := make(chan int, 1)
ch2 := make(chan int, 1)
ch1 <- 1
ch2 <- 2
select {
case v := <-ch1:
fmt.Println(v)
case v := <-ch2:
fmt.Println(v)
}
}
このとき、1 と 2 がランダムで出力されます。
これは select が どの case を実行するかをランダムに決定しているためです。
この記事では、具体的にどのようにランダムに決定しているかを解説します。
Go の select はどうやってランダムにchをセレクトしているのか
select 文の実際の処理は、Go のランタイム内部にある runtime/select.go の selectgo 関数で実装されています。
// runtime/select.go の中から抜粋&簡略化したもの
for i := 0; i < ncases; i++ {
j := cheaprandn(uint32(norder + 1))
pollorder[norder] = pollorder[j]
pollorder[j] = uint16(i)
norder++
}
// cheaprandn：乱数を取得するための関数
// pollorder：最初は要素ゼロで初期化された空の配列（スライス）
// ncases：default 含めたケースの数
// norder：初期値は 0
このselectgoを読み解くことで case を評価する際のランダム選択を理解していきます。
押さえるべきポイントは以下の 2 つです。
- case の評価順を表すスライス（pollorder）
- Fisher–Yates シャッフルを応用した配列要素のシャッフル
それぞれを順に見ていきます。
1. case の評価順を表すスライス（pollorder）
Go ランタイムは、pollorder という配列を用いて case の評価順を決定します。
たとえば次のような select 文があるとします。
select {
case <-ch0: // case 0
case <-ch1: // case 1
case <-ch2: // case 2
}
コンパイラはこの 3 つの case を内部で配列として保持します（インデックス 0〜2）。
そして Go のランタイムが作る pollorder は、「どの順番で case を評価するか」を表すスライスです。
例：pollorder = [2, 0, 1]の場合
| インデックス (i) | pollorder[i] | 意味 |
|---|---|---|
| 0 | 2 | 最初に case2 を評価する |
| 1 | 0 | 次に case0 を評価する |
| 2 | 1 | 最後に case1 を評価する |
-
pollorder[i]は「元の case 配列のどの case か」を表す -
iは「評価順序」を表す
つまり、実際に case の順序を見る際はこのpollorderを見ればいいんだ、と思ってもらえれば OK です。
2. Fisher–Yates シャッフルを応用した配列要素のシャッフル
この記事の肝はここです。
実行順序が入っているpollorderの中身を生成する際には、Fisher–Yates シャッフルを応用したアルゴリズムが用いられています。
Fisher–Yates シャッフルとは？
Fisher–Yates シャッフルは「配列の要素を完全にランダムに並び替える」ための有名なアルゴリズムらしいです。
標準的な Fisher–Yates シャッフルの仕組み（リストの末尾から先頭へ）:
// 既存の配列をシャッフルする場合
for i := n-1; i > 0; i-- {
j := rand(0, i+1) // 0からiまでのランダムな位置
swap(arr[i], arr[j]) // i番目とj番目を交換
}
- 配列の末尾から順番に処理
- 各要素について、その位置以前のどこかとランダムに入れ替える
- これを繰り返すことで、完全にシャッフルされた配列が完成
selectgo で使われている「応用版」アルゴリズム
selectgoでは標準的な Fisher–Yates シャッフルとは異なるアルゴリズムが用いられています。
インクリメンタルで挿入位置を変化させているのがポイントです:
標準的な Fisher-Yates シャッフルアルゴリズム:
// 既に存在する配列をシャッフル
arr := []int{0, 1, 2, 3}
for i := len(arr) - 1; i > 0; i-- {
j := rand(0, i+1)
swap(arr[i], arr[j]) // 後ろから交換していく
}
// 結果例: [2, 0, 3, 1]
応用版アルゴリズム:
// 空配列から要素を1つずつランダムに挿入
arr := []int{}
for i := 0; i < 4; i++ {
j := rand(0, len(arr)+1)
arr = append(arr, arr[j]) // j番目の要素を末尾にコピー
arr[j] = i // j番目に新要素を挿入
}
// 結果例: [2, 0, 3, 1]（同等のランダム性）
標準アルゴリズムと応用アルゴリズムの比較:
| 項目 | 標準 Fisher-Yates | selectgo 応用版 |
|---|---|---|
| 開始状態 |
[0, 1, 2, 3] (すべて存在) |
[] (空配列) |
| 処理 | 既存要素を交換 | 新しい要素をランダムな位置に挿入 |
| 操作イメージ | カードの山をシャッフル | カードを 1 枚ずつランダムに積む |
| コード | swap(arr[i], arr[j]) |
arr[末尾] = arr[j]; arr[j] = newvalue |
では、なぜ selectgo はこの方式を使うのでしょうか？
それは配列を事前に用意できないからです。
selectgo は配列を段階的に構築する必要があるため、[0,1,2,...] という配列を事前に作ることができません。そのため、「空配列に要素を 1 つずつランダムに追加していく」方式が必要になるのです。
pollorder 生成の具体例
select {
case <-ch0: // ← case 0
case <-ch1: // ← case 1
case <-ch2: // ← case 2
}
この select を実行すると、ランタイム内部では次のように pollorder が生成されます:
【初期状態】
pollorder = []
norder = 0
【i=0: case 0を追加】
j = cheaprandn(1) → 0
pollorder[0] = pollorder[0] // 何もなし
pollorder[0] = 0
→ [0]
【i=1: case 1を追加】
j = cheaprandn(2) → 1 (例)
pollorder[1] = pollorder[1] // 末尾に追加
pollorder[1] = 1
→ [0, 1]
【i=2: case 2を追加】
j = cheaprandn(3) → 0 (例)
pollorder[2] = pollorder[0] // 0番目の値(0)を末尾に退避
pollorder[0] = 2 // 0番目に新しい値(2)を挿入
→ [2, 1, 0]
まとめ
- Go の
select文におけるランダム選択は、配列pollorderによって決定される - pollorder を生成する際にはFisher-Yates シャッフル というランダムにシャッフルするアルゴリズムが使われている
- ただし、初期状態ではリストは空配列であるため配列を作りながらシャッフルするFisher-Yates シャッフルを応用したアルゴリズムが使われている
また、今回一度も取り上げることなくぬるっと使っていた乱数生成関数cheaprandnも通常の rand 関数よりも高速かつランダムに乱数を生成することができる素晴らしい仕組みです。
おわりに
Go のselect というシンプルな構文の裏側には、このような精緻なロジックが詰め込まれています。
今後も少しずつ勉強していって Golang ドヤトークに磨きをかけていこうと思います。
次回もお楽しみに。
Discussion