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

このコミットは、Go言語のmath/randパッケージにおけるPerm関数のマイナーな最適化に関するものです。Perm関数は、指定された範囲の整数（0からn-1まで）の擬似乱数順列を生成します。この変更は、Fisher-Yatesシャッフルアルゴリズムの「inside-out」実装を採用することで、既存の配列を初期化してからシャッフルするのではなく、順列を直接構築するように改善されています。これにより、特に大きな配列においてパフォーマンスが向上しています。

コミット

コミットハッシュ: 4a18e0edd94d156ebbccead44b553e2a436df5f5
作者: Josh Bleecher Snyder josharian@gmail.com
コミット日時: 2013年12月17日火曜日 13:49:34 +1100

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

https://github.com/golang/go/commit/4a18e0edd94d156ebbccead44b553e2a436df5f5

元コミット内容

math/rand: minor optimization to Perm

Instead of writing out 0..n and then reading it
back, just use i when it is needed.

Wikipedia calls this the "inside-out" implementation:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

This yields identical values to the previous
implementation, given the same seed. (Note that the
output from Example_rand is unchanged.)

2.8 GHz Intel Core i7, results very stable:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3           138          136   -1.45%
BenchmarkPerm30          825          803   -2.67%

Stock Raspberry Pi, minimum improvement out of three runs:

benchmark          old ns/op    new ns/op    delta
BenchmarkPerm3          5774         5664   -1.91%
BenchmarkPerm30        32582        29381   -9.82%

R=golang-dev, dave, mtj, adg
CC=golang-dev
https://golang.org/cl/21030043

変更の背景

このコミットの主な目的は、math/randパッケージのPerm関数のパフォーマンスを向上させることです。以前の実装では、まず0からn-1までの整数で構成されるスライスを初期化し、その後、そのスライスに対してFisher-Yatesシャッフルを適用していました。この二段階のアプローチは、特にnが大きい場合に不要なメモリ書き込みと読み込みのオーバーヘッドを発生させていました。

コミットメッセージにもあるように、この変更はFisher-Yatesシャッフルアルゴリズムの「inside-out」実装を採用しています。この「inside-out」アプローチは、シャッフルされた順列を最初から構築することで、中間的な初期化ステップを排除します。これにより、メモリ操作が削減され、全体的な実行速度が向上します。ベンチマーク結果が示すように、特にnの値が大きい場合に顕著な改善が見られます。

前提知識の解説

擬似乱数順列 (Pseudo-random Permutation)

擬似乱数順列とは、特定のアルゴリズム（擬似乱数生成器）によって生成される、要素のランダムな並び替えのことです。真の乱数とは異なり、同じシード値（初期値）を与えれば常に同じ順列が生成されます。これは、再現性が必要なテストやシミュレーションにおいて重要です。

Fisher-Yatesシャッフル (Fisher-Yates Shuffle)

Fisher-Yatesシャッフルは、有限なシーケンスの要素をランダムに並べ替えるためのアルゴリズムです。このアルゴリズムは、すべての可能な順列が等しい確率で生成されることを保証します。

基本的な（in-place）Fisher-Yatesシャッフル:

配列の最後の要素から開始し、最初の要素まで逆順にループします。
現在の要素（インデックスi）について、0からiまでのランダムなインデックスjを選択します。
現在の要素とインデックスjの要素を交換します。

これにより、各要素がランダムな位置に配置され、最終的に配列全体がシャッフルされます。

Fisher-Yatesシャッフルの「Inside-Out」実装

「Inside-Out」バージョンのFisher-Yatesシャッフルは、既存の配列をその場でシャッフルするのではなく、新しいシャッフルされた配列をゼロから構築するバリアントです。この方法は、元のシーケンスを保持する必要がある場合に特に有用です。

「Inside-Out」実装のステップ:

空の結果配列（または、このGoのPerm関数の場合は、make([]int, n)で初期化されたスライス）を準備します。
入力配列（この場合は0からn-1までの論理的なシーケンス）の各要素について、順方向（i = 0からn-1まで）にループします。
現在の要素iについて、0から現在の結果配列のサイズ（i）までのランダムなインデックスjを生成します。
もしjが現在の結果配列のサイズ（i）と等しい場合、現在の要素iを結果配列の末尾に追加します。
もしjが現在の結果配列のサイズ（i）より小さい場合、結果配列のインデックスjにある要素を結果配列の末尾にコピーします。その後、現在の要素iを結果配列のインデックスjに配置します。

このプロセスにより、結果配列は要素が追加されるにつれてシャッフルされた状態を維持します。Perm関数の場合、m[i]はi番目の要素が最終的に配置される場所を指し、m[j]はj番目の要素が一時的に移動される場所を指します。

技術的詳細

このコミットは、src/pkg/math/rand/rand.goファイルのPerm関数を変更しています。

変更前:

func (r *Rand) Perm(n int) []int {
	m := make([]int, n)
	for i := 0; i < n; i++ {
		m[i] = i // 0からn-1までの値を初期化
	}
	for i := 0; i < n; i++ {
		j := r.Intn(i + 1)
		m[i], m[j] = m[j], m[i] // Fisher-Yatesシャッフル（in-place）
	}
	return m
}

変更前は、まずmスライスを0からn-1までの値で埋め、その後、通常のFisher-Yatesシャッフル（in-place）を実行していました。これは2つのループを必要とし、最初のループで不要な書き込みが発生していました。

変更後:

func (r *Rand) Perm(n int) []int {
	m := make([]int, n)
	// 最初の初期化ループが削除された
	for i := 0; i < n; i++ {
		j := r.Intn(i + 1)
		m[i] = m[j] // m[j]の値をm[i]にコピー
		m[j] = i    // iの値をm[j]に配置
	}
	return m
}

変更後では、最初のforループが削除され、mスライスはmake([]int, n)でゼロ値（Goの場合、int型はデフォルトで0）で初期化されるだけになります。シャッフルロジックは単一のループ内で完結し、Fisher-Yatesシャッフルの「inside-out」バージョンを実装しています。

具体的には、ループの各イテレーションiにおいて：

j := r.Intn(i + 1): 0からiまでのランダムなインデックスjを生成します。
m[i] = m[j]: 現在のm[j]の値をm[i]にコピーします。これは、jがiより小さい場合、既にシャッフルされた要素のいずれかを現在の位置iに移動させることを意味します。もしjがiと等しい場合、m[i]は自分自身にコピーされます（実質的に何もしない）。
m[j] = i: 現在の論理的な要素i（つまり、0からn-1までのシーケンスのi番目の値）をm[j]に配置します。

このロジックにより、mスライスはループが進むにつれて、0からiまでの要素のランダムな順列を常に保持するようになります。最終的にループが終了すると、mは0からn-1までのすべての要素のランダムな順列を含んでいます。

この最適化により、初期化のための余分なループが不要になり、メモリへの書き込み回数が削減されます。ベンチマーク結果は、この変更がパフォーマンスに良い影響を与えていることを明確に示しています。特に、Raspberry Piのようなリソースが限られた環境では、より大きな改善が見られます。これは、メモリ帯域幅やキャッシュの効率が向上したためと考えられます。

また、src/pkg/math/rand/rand_test.goには、Perm関数のベンチマークテストが追加されています。BenchmarkPerm3とBenchmarkPerm30は、それぞれn=3とn=30の場合のPerm関数のパフォーマンスを測定するために使用されます。これらのテストは、最適化の効果を定量的に評価するために不可欠です。

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

diff --git a/src/pkg/math/rand/rand.go b/src/pkg/math/rand/rand.go
index 2157cdb465..04fb67d19d 100644
--- a/src/pkg/math/rand/rand.go
+++ b/src/pkg/math/rand/rand.go
@@ -103,12 +103,10 @@ func (r *Rand) Float32() float32 { return float32(r.Float64()) }
 // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
 func (r *Rand) Perm(n int) []int {
 	m := make([]int, n)
-	for i := 0; i < n; i++ {
-		m[i] = i
-	}
 	for i := 0; i < n; i++ {
 		j := r.Intn(i + 1)
-		m[i], m[j] = m[j], m[i]
+		m[i] = m[j]
+		m[j] = i
 	}
 	return m
 }
diff --git a/src/pkg/math/rand/rand_test.go b/src/pkg/math/rand/rand_test.go
index 4d3abdb606..4f0a8d0ee9 100644
--- a/src/pkg/math/rand/rand_test.go
+++ b/src/pkg/math/rand/rand_test.go
@@ -357,3 +357,17 @@ func BenchmarkInt31n1000(b *testing.B) {
 		r.Int31n(1000)
 	}
 }
+
+func BenchmarkPerm3(b *testing.B) {
+	r := New(NewSource(1))
+	for n := b.N; n > 0; n-- {
+		r.Perm(3)
+	}
+}
+
+func BenchmarkPerm30(b *testing.B) {
+	r := New(NewSource(1))
+	for n := b.N; n > 0; n-- {
+		r.Perm(30)
+	}
+}

コアとなるコードの解説

src/pkg/math/rand/rand.goのPerm関数において、以下の変更が行われました。

初期化ループの削除:
```
-	for i := 0; i < n; i++ {
-		m[i] = i
-	}
```
この削除されたループは、mスライスを0からn-1までの連続した整数で初期化していました。この初期化は、Fisher-Yatesシャッフルの「inside-out」実装では不要になります。make([]int, n)によってスライスが作成された時点で、要素はGoのデフォルト値である0で初期化されますが、これは「inside-out」アルゴリズムの動作に影響しません。
シャッフルロジックの変更:
```
-		m[i], m[j] = m[j], m[i]
+		m[i] = m[j]
+		m[j] = i
```
これは、Fisher-Yatesシャッフルの「in-place」交換から「inside-out」ロジックへの変更です。
- m[i] = m[j]: これは、現在のインデックスiに、ランダムに選ばれた過去のインデックスj（0 <= j <= i）の値をコピーします。もしj == iであれば、m[i]は自分自身にコピーされます。もしj < iであれば、既にシャッフルされた部分からランダムな要素がm[i]に移動されます。
- m[j] = i: これは、現在の論理的な要素i（つまり、0からn-1までのシーケンスのi番目の値）を、ランダムに選ばれたインデックスjに配置します。これにより、iがシャッフルされたスライスに組み込まれます。

この2つの行の組み合わせにより、スライスmは、ループの各ステップで0からiまでの要素の有効なランダム順列を維持します。

src/pkg/math/rand/rand_test.goには、以下のベンチマーク関数が追加されました。

BenchmarkPerm3:

func BenchmarkPerm3(b *testing.B) {
	r := New(NewSource(1))
	for n := b.N; n > 0; n-- {
		r.Perm(3)
	}
}

これは、Perm関数がn=3の場合のパフォーマンスを測定します。

BenchmarkPerm30:
```
func BenchmarkPerm30(b *testing.B) {
	r := New(NewSource(1))
	for n := b.N; n > 0; n-- {
		r.Perm(30)
	}
}
```
これは、Perm関数がn=30の場合のパフォーマンスを測定します。これらのベンチマークは、変更が小規模な入力と中規模な入力の両方でどのように機能するかを評価するために使用されます。コミットメッセージのベンチマーク結果は、これらのテストの実行によって得られたものです。

comemo