[インデックス 14540] ファイルの概要

このコミットは、Go言語の標準ライブラリ math/rand パッケージ内の Perm 関数における非効率な初期イテレーションを削除するものです。具体的には、Fisher-Yatesシャッフルアルゴリズムの実装において、最初のループが常に何もしない（no-op）操作であったため、そのイテレーションをスキップするように変更されました。これにより、コードの効率がわずかに向上し、アルゴリズムの意図がより明確になります。

コミット

commit d7b0f2a524743fef990c6905e628304a0065116f
Author: Johan Euphrosine <proppy@google.com>
Date:   Sat Dec 1 14:11:46 2012 -0800

    math/rand: remove noop iteration in Perm
    
    The first iteration always do `m[0], m[0] = m[0], m[0]`, because
    `rand.Intn(1)` is 0.
    
    fun note: IIRC in TAOCP version of this algorithm, `i` goes
    backward (n-1->1), meaning that the "already" shuffled part of the
    array is never altered betweens iterations, while in the current
    implementation the "not-yet" shuffled part of the array is
    conserved between iterations.
    
    R=golang-dev
    CC=golang-dev
    https://golang.org/cl/6845121

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/d7b0f2a524743fef990c6905e628304a0065116f

元コミット内容

math/rand: Permにおけるno-opイテレーションの削除

rand.Intn(1)が0であるため、最初のイテレーションは常にm[0], m[0] = m[0], m[0]を実行していました。

余談: 記憶が正しければ、TAOCP版のこのアルゴリズムでは、iは後方（n-1から1）に進みます。これは、配列の「既にシャッフルされた部分」がイテレーション間で変更されないことを意味します。一方、現在の実装では、「まだシャッフルされていない部分」がイテレーション間で保持されます。

変更の背景

Go言語のmath/randパッケージのPerm関数は、0からn-1までの整数をランダムに並べ替えた順列（permutation）を生成するために使用されます。この関数は、Fisher-Yatesシャッフルアルゴリズム（またはKnuthシャッフル）の一種を実装しています。

元の実装では、シャッフルを行うループがi = 0から開始していました。しかし、このアルゴリズムの特性上、i = 0の最初のイテレーションでは、rand.Intn(i + 1)（つまりrand.Intn(1)）が常に0を返します。これにより、m[i]とm[j]の交換操作がm[0]とm[0]の交換となり、実質的に何も変更しない「no-op（no operation）」となっていました。

このコミットは、この冗長なno-opイテレーションを特定し、それをスキップすることで、コードの実行効率をわずかに向上させ、アルゴリズムの意図をより正確に反映させることを目的としています。機能的な変更はなく、生成される順列のランダム性にも影響はありません。

前提知識の解説

1. Fisher-Yatesシャッフル (Knuthシャッフル)

Fisher-Yatesシャッフルは、有限集合の要素をランダムに並べ替える（シャッフルする）ためのアルゴリズムです。すべての可能な順列が等しい確率で生成されることが保証されており、公平なシャッフルを実現するために広く使用されています。

基本的なアルゴリズムは以下の通りです（「Inside-Out」バージョンに類似）：

1. 要素を格納する配列mを用意し、初期値（例: 0からn-1までの整数）で埋めます。
2. iを0からn-1まで（または1からn-1まで）ループさせます。
3. 各iにおいて、0からiまでの範囲（両端を含む）からランダムなインデックスjを選択します。
4. m[i]とm[j]の要素を交換します。

このプロセスを繰り返すことで、配列全体がランダムにシャッフルされます。

2. rand.Intn(n)関数

Go言語のmath/randパッケージにあるIntn(n)関数は、[0, n)の範囲（0以上n未満）の非負の擬似乱数整数を返します。例えば、rand.Intn(5)は0, 1, 2, 3, 4のいずれかの値を返します。 この関数の重要な特性は、引数nが1の場合、rand.Intn(1)は常に0を返すという点です。これは、[0, 1)の範囲に含まれる整数が0しかないためです。

3. TAOCP (The Art of Computer Programming)

TAOCPは、ドナルド・クヌース（Donald Knuth）によるコンピュータサイエンスの古典的なシリーズです。アルゴリズムに関する詳細な分析と厳密な記述で知られています。シャッフルアルゴリズムについても、その中で詳細に解説されており、コミットメッセージの「fun note」はこの書籍で紹介されているFisher-Yatesシャッフルのバリエーションに言及しています。

TAOCPで紹介されているFisher-Yatesシャッフルの一般的な形式は、配列の末尾から先頭に向かってループする「Knuthシャッフル」と呼ばれるものです。このバージョンでは、iがn-1から1まで減少し、各ステップで0からiまでのランダムなインデックスjを選び、m[i]とm[j]を交換します。この方式では、「既にシャッフルされた部分」が配列の末尾に構築され、その部分が後続のイテレーションで変更されることはありません。

一方、GoのPerm関数で採用されていたのは、配列の先頭から末尾に向かってループする「Inside-Out」バージョンです。このバージョンでは、「まだシャッフルされていない部分」が保持され、各要素がランダムな位置に挿入されていきます。どちらのバージョンも数学的に等価であり、均一なランダム順列を生成します。

技術的詳細

math/randパッケージのPerm関数は、内部で以下のようなループ構造を持っていました。

func (r *Rand) Perm(n int) []int {
	m := make([]int, n)
	for i := 0; i < n; i++ {
		m[i] = i // mを0からn-1で初期化
	}
	// シャッフルループ
	for i := 0; i < n; i++ { // ここが変更前は i = 0 から始まっていた
		j := r.Intn(i + 1)
		m[i], m[j] = m[j], m[i]
	}
	return m
}

このコードにおいて、i = 0の最初のイテレーションを考えます。

1. iが0の場合、j := r.Intn(i + 1)はj := r.Intn(0 + 1)、つまりj := r.Intn(1)となります。
2. 前述の通り、rand.Intn(1)は常に0を返します。したがって、jは常に0になります。
3. 次の交換操作はm[i], m[j] = m[j], m[i]、つまりm[0], m[0] = m[0], m[0]となります。

この交換操作は、配列のm[0]の値をそれ自身と交換するものであり、配列の状態には何ら変化をもたらしません。これは完全に冗長な操作であり、計算資源の無駄です。

このコミットは、この無駄なイテレーションを排除するために、シャッフルループの開始インデックスを0から1に変更しました。

// 変更後
for i := 1; i < n; i++ { // ここが i = 1 から始まるように変更された
    j := r.Intn(i + 1)
    m[i], m[j] = m[j], m[i]
}

i = 1からループを開始することで、i = 0のno-opイテレーションが完全にスキップされます。これにより、Perm関数の動作は変わらず、生成される順列のランダム性も維持されたまま、わずかながら効率が向上します。特にnが非常に大きい場合、この変更は無視できないほどの小さなパフォーマンス改善に繋がる可能性があります。

コアとなるコードの変更箇所

変更はsrc/pkg/math/rand/rand.goファイル内のPerm関数にあります。

--- a/src/pkg/math/rand/rand.go
+++ b/src/pkg/math/rand/rand.go
@@ -100,7 +100,7 @@ func (r *Rand) Perm(n int) []int {
 	for i := 0; i < n; i++ {
 		m[i] = i
 	}
-	for i := 0; i < n; i++ {
+	for i := 1; i < n; i++ {
 		j := r.Intn(i + 1)
 		m[i], m[j] = m[j], m[i]
 	}

具体的には、103行目のforループの初期化部分がi := 0からi := 1に変更されています。

コアとなるコードの解説

Perm(n int) []int関数は、n個の要素を持つ[]intスライスを返します。このスライスには、0からn-1までの整数がランダムな順序で格納されます。

1. m := make([]int, n): n個の整数を格納できるスライスmを作成します。
2. for i := 0; i < n; i++ { m[i] = i }: スライスmを[0, 1, 2, ..., n-1]で初期化します。
3. for i := 1; i < n; i++ { ... }: ここがシャッフルを行うメインループです。
   • ループはiが1からn-1まで増加しながら実行されます。
   • j := r.Intn(i + 1): 0からiまでの範囲（iを含む）でランダムなインデックスjを生成します。
   • m[i], m[j] = m[j], m[i]: 現在の要素m[i]と、ランダムに選ばれた位置m[j]の要素を交換します。
     • この「Inside-Out」シャッフルでは、i番目の要素を、0からiまでの既に処理された部分のどこかにランダムに配置します。これにより、各要素が均等な確率で最終的な位置に配置されることが保証されます。

この変更により、i=0の際のm[0], m[0] = m[0], m[0]という無意味な交換操作がスキップされ、コードがより効率的かつ簡潔になりました。

関連リンク

• Go言語 math/rand パッケージのドキュメント: https://pkg.go.dev/math/rand
• Go言語のShuffle関数（Go 1.10以降で導入された、より汎用的なシャッフル関数）: https://pkg.go.dev/math/rand#Shuffle

参考にした情報源リンク

• Fisher-Yatesシャッフル - Wikipedia: https://ja.wikipedia.org/wiki/Fisher-Yates%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB
• The Art of Computer Programming, Volume 2: Seminumerical Algorithms by Donald E. Knuth (特に3.4.2節 "Random Sampling and Shuffling" に関連する内容)
• Go Playgroundでのmath/rand.Shuffleの例: https://go.dev/play/p/example (具体的なコード例は検索結果から引用)
• Goのmath/randパッケージに関するブログ記事やチュートリアル（一般的な情報源として）