0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

技術トークでドヤるために Go の select を深ぼってみた

Posted at

はじめに

先日の記事で Go の select についての問題を出題しました。
【Go 腕試し】複数チャネルの select

この記事はその深掘り解説みたいなものです。

Go のランタイムが実装されているruntime/select.go のコードを読み解き、select が準備万端な ch をどのように ランダム選択 しているかを解説します。


select のランダム選択を簡単におさらい

以下のコードでは、ch1ch2 の両方が送信済みで、どちらも受信可能な状態です。

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.goselectgo 関数で実装されています。

// 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 つです。

  1. case の評価順を表すスライス(pollorder)
  2. 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番目を交換
}
  1. 配列の末尾から順番に処理
  2. 各要素について、その位置以前のどこかとランダムに入れ替える
  3. これを繰り返すことで、完全にシャッフルされた配列が完成

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 ドヤトークに磨きをかけていこうと思います。
次回もお楽しみに。

参考資料

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?