Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリである src/pkg/math/rand/rand.go ファイルに対する変更です。このファイルは、擬似乱数生成器（PRNG）の実装を含んでおり、rand.Perm 関数など、乱数に関連する機能を提供します。rand.Perm(n) 関数は、0からn-1までの整数をランダムに並べ替えたスライスを生成するために使用されます。

コミット

このコミットは、以前のコミットである CL 6845121 (コミットハッシュ 79603a5e4cda) を元に戻す（undo）ものです。元のコミットは math/rand パッケージの Perm 関数における「noop iteration（何もしない繰り返し）」を削除することを目的としていましたが、この変更がGo 1.0とGo 1.1間での乱数生成の互換性を損なうことが判明したため、元に戻されました。

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

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

元コミット内容

元に戻されたコミット CL 6845121 (ハッシュ 79603a5e4cda) の内容は、math/rand: remove noop iteration in Perm というものでした。この変更は、rand.Perm 関数内で発生していた、最初のイテレーションが常に m[0], m[0] = m[0], m[0] となる「何もしない」操作を削除することを目的としていました。これは rand.Intn(1) が常に 0 を返すためです。

元のコミットの説明には、Fisher-YatesシャッフルアルゴリズムのTAOCP（The Art of Computer Programming）版では i が逆方向に進む（n-1から1へ）ことで、「既にシャッフルされた部分」がイテレーション間で変更されないのに対し、現在の実装では「まだシャッフルされていない部分」が保存されるという興味深い注記も含まれていました。

変更の背景

このコミットの主な背景は、Go 1.0とGo 1.1の間で rand.Seed(0) を使用した際の rand.Perm(100) の出力に互換性を持たせる必要があったことです。

Go言語の標準ライブラリ、特に math/rand のようなパッケージでは、バージョン間で互換性を維持することが非常に重要です。これは、同じシード値を与えた場合に、異なるGoのバージョンであっても同じ擬似乱数列が生成されることを保証するためです。このような保証は、再現可能なテスト、シミュレーション、または特定のアルゴリズムの動作を予測可能にするために不可欠です。

元の CL 6845121 は、Perm 関数の内部的な最適化を意図していましたが、結果として乱数生成のシーケンスが変更されてしまいました。これにより、Go 1.0で生成された乱数列とGo 1.1で生成された乱数列が、同じシード値を与えても異なってしまうという問題が発生しました。この非互換性は、既存のコードやテストが予期しない動作をする原因となるため、Goチームは元の変更を元に戻すことを決定しました。

前提知識の解説

math/rand パッケージの概要

math/rand パッケージは、Go言語で擬似乱数を生成するための機能を提供します。擬似乱数とは、完全にランダムではないものの、統計的にはランダムに見える数列のことです。これらの数列は、初期値（シード）に基づいて決定論的に生成されます。

rand.Seed() の役割

rand.Seed(seed int64) 関数は、擬似乱数生成器のシード値を設定します。シード値は、乱数列の開始点となる数値です。同じシード値を与えれば、常に同じ乱数列が生成されます。これにより、乱数を使用するプログラムの動作を再現可能にすることができます。rand.Seed(0) は、特定の初期状態に乱数生成器をリセットする一般的な方法として使用されます。

rand.Perm() の役割とFisher-Yatesシャッフルアルゴリズム

rand.Perm(n int) 関数は、[0, n-1] の範囲の整数をランダムに並べ替えた新しいスライスを返します。この関数は、Fisher-Yatesシャッフル（またはKnuthシャッフル）アルゴリズムに基づいて実装されています。

Fisher-Yatesシャッフルアルゴリズムの基本的な考え方:

  1. 要素が n 個ある配列 m を用意します。最初は m[i] = i とします。
  2. i を 0 から n-1 まで（または n-1 から 0 まで）ループさせます。
  3. 各イテレーションで、0 から i までの範囲（または 0 から現在の i までの範囲）からランダムなインデックス j を選択します。
  4. m[i] と m[j] の要素を交換します。

このプロセスにより、配列の要素がランダムにシャッフルされます。

Go 1.0とGo 1.1間の互換性の重要性

Go言語は、後方互換性を非常に重視しています。これは、新しいバージョンのGoコンパイラやランタイムを使用しても、以前のバージョンで書かれたコードが引き続き正しく動作することを意味します。特に、標準ライブラリのAPIやその動作は、既存のユーザーのコードを壊さないように、慎重に管理されます。乱数生成器のような決定論的な動作が期待されるコンポーネントにおいては、同じ入力（シード）に対して同じ出力（乱数列）が保証されることが、互換性の重要な側面となります。

技術的詳細

rand.Perm 関数の実装における問題は、Fisher-Yatesシャッフルアルゴリズムのループの開始インデックスにありました。

元の Perm 関数の実装（CL 6845121 が適用される前）では、シャッフルループは for i := 0; i < n; i++ で始まり、各イテレーションで j := r.Intn(i + 1) を使用していました。

ここで問題となるのは、i = 0 の最初のイテレーションです。このとき、r.Intn(i + 1) は r.Intn(1) となります。rand.Intn(k) は [0, k-1] の範囲の乱数を生成するため、rand.Intn(1) は常に 0 を返します。したがって、j は常に 0 となります。

これにより、最初のイテレーションでは m[0], m[0] = m[0], m[0] という操作が行われます。これは、要素 m[0] をそれ自身と交換するものであり、配列の状態には何の影響も与えません。この操作は「noop iteration（何もしない繰り返し）」と呼ばれます。

CL 6845121 は、この「noop iteration」を削除するために、ループを for i := 1; i < n; i++ に変更しました。これにより、i = 0 の場合の無駄な交換がスキップされ、パフォーマンスのわずかな向上が期待されました。

しかし、この変更は、rand.Intn の呼び出しシーケンスを変更してしまいました。乱数生成器は、呼び出されるたびに内部状態を更新します。ループの開始インデックスを 0 から 1 に変更したことで、rand.Intn の最初の呼び出しがスキップされ、その後の乱数列がGo 1.0の動作と異なってしまう結果となりました。

Go 1.0とGo 1.1の間で rand.Seed(0) と rand.Perm(100) の出力が異なるという問題は、この rand.Intn の呼び出しシーケンスの変更が原因でした。互換性を維持するためには、たとえ「noop」な操作であっても、乱数生成器の内部状態に影響を与える呼び出しは維持する必要がありました。

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

--- 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 := 1; i < n; i++ {
+	for i := 0; i < n; i++ {
 		j := r.Intn(i + 1)
 		m[i], m[j] = m[j], m[i]
 	}

コアとなるコードの解説

このコミットのコアとなる変更は、Perm 関数内のシャッフルループの開始インデックスを元に戻すことです。

変更前（CL 6845121 適用後）:

	for i := 1; i < n; i++ {
		j := r.Intn(i + 1)
		m[i], m[j] = m[j], m[i]
	}

変更後（このコミットで元に戻された状態）:

	for i := 0; i < n; i++ {
		j := r.Intn(i + 1)
		m[i], m[j] = m[j], m[i]
	}

この変更により、ループは i = 0 から開始されるようになります。前述の通り、i = 0 の場合、j = r.Intn(0 + 1) すなわち r.Intn(1) となり、j は常に 0 になります。結果として m[0] と m[0] が交換されるという「noop iteration」が再び発生します。

この「noop iteration」は配列の状態には影響を与えませんが、r.Intn が一度呼び出されることで、乱数生成器の内部状態が更新されます。この更新が、Go 1.0とGo 1.1の間で rand.Seed(0) を使用した際の rand.Perm(100) の出力の互換性を維持するために不可欠でした。

つまり、この変更はパフォーマンスの微細な最適化よりも、Go言語のバージョン間での乱数生成の決定論的な互換性を優先した結果です。

関連リンク

特になし。

参考にした情報源リンク

  • コミットメッセージ: ff2534e076a01445f5852f0fab7a3017ee65c8ba
  • Go言語の math/rand パッケージのドキュメント (現在のバージョン): https://pkg.go.dev/math/rand
  • Fisher-Yatesシャッフルアルゴリズムに関する一般的な情報源。