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

このコミットは、Go言語の標準ライブラリであるrandパッケージに、指定された範囲の整数をランダムに並べ替える（順列を生成する）機能を追加するものです。具体的には、perm(n int) *map[int]intという関数が導入され、0からn-1までの整数を要素とするマップをランダムにシャッフルした結果を返します。これは、ランダムなサンプリングや要素の順序を無作為化する際に利用される基本的な機能です。

コミット

commit 2567c073ea230cf96078477be117f07a16e93470
Author: Ken Thompson <ken@golang.org>
Date:   Sun Nov 16 13:02:47 2008 -0800

    random permutation function
    func perm(n int) *map[int]int
    
    R=r
    OCL=19340
    CL=19340

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

https://github.com/golang/go/commit/2567c073ea230cf96078477be117f07a16e93470

元コミット内容

このコミットの元々の内容は、Go言語のrandパッケージに「ランダムな順列関数」を追加するというものです。具体的には、perm(n int) *map[int]intというシグネチャを持つ関数が導入され、これはn個の要素のランダムな順列を生成することを目的としています。コミットメッセージには、Go言語の初期開発における内部的なレビュープロセスを示すR=r（Reviewed by r）や、変更リスト番号であるOCL（Original Change List）とCL（Change List）が含まれています。

変更の背景

Go言語の初期段階において、標準ライブラリは基本的な機能から順次整備されていました。乱数生成は多くのアプリケーションで必要とされる基本的な機能であり、単に乱数を生成するだけでなく、コレクションの要素をランダムに並べ替えたり、特定の範囲の数値のランダムな順列を得たりする機能も重要です。

このperm関数の追加は、以下のような背景が考えられます。

基本的なユーティリティの提供: プログラミングにおいて、配列やリストの要素をランダムにシャッフルする、あるいは特定の範囲の数値のランダムな順列を生成するニーズは非常に一般的です。このような基本的なユーティリティを標準ライブラリとして提供することで、開発者が独自に実装する手間を省き、より堅牢で効率的なコードを書けるようにすることが目的です。
統計的サンプリングやシミュレーション: 統計的なサンプリング、モンテカルロシミュレーション、ゲーム開発など、ランダムな順序付けが必要な多くのシナリオで、この関数は基盤となります。
Go言語の設計思想: Go言語は「シンプルさ」と「実用性」を重視しており、よく使われる機能は標準ライブラリに含めるという設計思想があります。perm関数もその一環として追加されたと考えられます。

前提知識の解説

1. ランダムな順列（Random Permutation）

ランダムな順列とは、ある集合の要素をすべて使用して、それらをランダムな順序で並べ替えたものです。例えば、集合 {0, 1, 2} のランダムな順列には、{0, 1, 2}、{0, 2, 1}、{1, 0, 2}、{1, 2, 0}、{2, 0, 1}、{2, 1, 0} などがあります。すべての可能な順列が等しい確率で生成されることが、真に「ランダムな」順列であるための条件です。

2. Go言語の`map`型

Go言語のmapは、キーと値のペアを格納するハッシュテーブル（連想配列）です。map[KeyType]ValueTypeのように宣言され、KeyTypeは比較可能な型（整数、文字列など）、ValueTypeは任意の型です。このコミットで使われているmap[int]intは、整数をキーとし、整数を値とするマップを意味します。

3. Fisher-Yatesシャッフルアルゴリズム（またはKnuthシャッフル）

Fisher-Yatesシャッフルは、有限集合の要素をランダムに並べ替えるためのアルゴリズムです。このアルゴリズムは、すべての可能な順列を等しい確率で生成するという点で、統計的に公平なシャッフルを提供します。

基本的な手順は以下の通りです（配列aの要素をシャッフルする場合）：

配列の最後の要素から最初の要素まで（またはその逆）を順に見ていく。
現在の要素iについて、0からiまでのランダムなインデックスjを選択する。
要素a[i]とa[j]を交換する。

このコミットのperm関数は、このFisher-Yatesシャッフルアルゴリズムの変形をmapに対して適用しているように見えます。

技術的詳細

perm関数は、nという整数を受け取り、0からn-1までの整数をキーと値に持つmap[int]intのポインタを返します。このマップは、初期状態ではm[i] = iという形で、キーと値が一致するエントリがn個格納されています。

関数の実装は以下のステップで行われます。

m := new(map[int]int);
- map[int]int型の新しいマップを生成し、そのポインタをmに代入します。Go言語のマップは参照型ですが、ここではnewを使ってポインタとして扱っています。これはGo言語の初期のコードスタイルや、特定のメモリ管理の意図があった可能性があります。現代のGoでは通常make(map[int]int)を使用します。
for i:=0; i<n; i++ { m[i] = i; }
- 0からn-1までの各整数iに対して、マップmにiをキーとし、iを値とするエントリを追加します。これにより、マップは{0:0, 1:1, ..., n-1:n-1}という初期状態になります。
for i:=0; i<n; i++ { j := nrand(n); t := m[i]; m[i] = m[j]; m[j] = t; }
- このループが、マップの値をランダムにシャッフルする核心部分です。
- iは0からn-1まで順に進みます。
- j := nrand(n);
  - nrand(n)は、0以上n未満のランダムな整数を生成する関数です。これはrandパッケージ内の別の関数であり、このコミットの差分には含まれていませんが、乱数生成の基盤となります。
  - jは、0からn-1までのランダムなインデックス（キー）として選ばれます。
- t := m[i]; m[i] = m[j]; m[j] = t;
  - これは、マップのキーiに対応する値m[i]と、ランダムに選ばれたキーjに対応する値m[j]を交換する操作です。
  - 一時変数tを使って値を保持し、m[i]にm[j]の値を、m[j]にt（元のm[i]の値）を代入しています。

このシャッフルアルゴリズムは、Fisher-Yatesシャッフルに非常に似ています。ただし、一般的なFisher-Yatesシャッフルが配列の要素を交換するのに対し、ここではマップの値を交換しています。キーは0からn-1まで固定されており、それに対応する値がランダムに並べ替えられることで、結果的に0からn-1までの数値のランダムな順列がマップの値として得られます。

例えば、perm(3)を呼び出した場合：初期状態: m = {0:0, 1:1, 2:2}

i = 0:
- jがランダムに選ばれる（例: j = 2）
- m[0] (値は0) と m[2] (値は2) を交換
- mは {0:2, 1:1, 2:0} になる
i = 1:
- jがランダムに選ばれる（例: j = 0）
- m[1] (値は1) と m[0] (値は2) を交換
- mは {0:1, 1:2, 2:0} になる
i = 2:
- jがランダムに選ばれる（例: j = 2）
- m[2] (値は0) と m[2] (値は0) を交換（変化なし）
- mは {0:1, 1:2, 2:0} になる

最終的に返されるマップの値は、{1, 2, 0}という0, 1, 2のランダムな順列になります。このアルゴリズムは、すべての順列を等しい確率で生成するため、統計的に公平な結果が得られます。

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

src/lib/rand.goファイルに以下の変更が加えられました。

--- a/src/lib/rand.go
+++ b/src/lib/rand.go
@@ -14,6 +14,7 @@ package	rand
 // urand32 - return random uint32
 // nrand, nrand31, nrand63 - return 0 <= random < n
 // frand, frand64, frand32 - return 0 <= random float, float64, float32 < 1
+// perm gives a random permutation map[int]int
 
 const
 (
@@ -162,6 +163,22 @@ frand() float
 	return float(frand64())
 }
 
+export func
+perm(n int) *map[int]int
+{
+	m := new(map[int]int);
+	for i:=0; i<n; i++ {
+		m[i] = i;
+	}
+	for i:=0; i<n; i++ {
+		j := nrand(n);
+		t := m[i];
+		m[i] = m[j];
+		m[j] = t;
+	}
+	return m;
+}
+
 func
 init()
 {

コアとなるコードの解説

変更は主にsrc/lib/rand.goファイルに集中しており、以下の2つの主要な追加があります。

コメントの追加:
```
// perm gives a random permutation map[int]int
```
既存の乱数生成関数の説明コメント群に、perm関数がmap[int]int形式でランダムな順列を提供することを示す行が追加されました。これにより、この関数の目的が明確になります。
perm関数の実装:
```
export func
perm(n int) *map[int]int
{
	m := new(map[int]int);
	for i:=0; i<n; i++ {
		m[i] = i;
	}
	for i:=0; i<n; i++ {
		j := nrand(n);
		t := m[i];
		m[i] = m[j];
		m[j] = t;
	}
	return m;
}
```
- export func perm(n int) *map[int]int:
  - exportキーワードは、この関数がパッケージ外からアクセス可能であることを示します。Go言語の初期の構文であり、現在のGoでは関数名が大文字で始まることでエクスポートされます（例: Perm）。
  - permは関数名。
  - n intは、順列を生成する要素の数（0からn-1までの範囲）を指定する整数型の引数。
  - *map[int]intは、整数をキーとし、整数を値とするマップへのポインタを戻り値とすることを示します。
- m := new(map[int]int);:
  - 新しい空のmap[int]intを生成し、そのポインタをmに代入します。
- for i:=0; i<n; i++ { m[i] = i; }:
  - 最初のループでは、マップmを初期化します。iが0からn-1まで増加するにつれて、m[0]=0, m[1]=1, ..., m[n-1]=n-1というエントリが作成されます。これにより、マップは順序付けられた状態になります。
- for i:=0; i<n; i++ { ... }:
  - 2番目のループがシャッフル処理を行います。iは0からn-1まで順に進みます。
  - j := nrand(n);: 0からn-1までの範囲でランダムな整数jを生成します。このjは、交換対象となるマップのキー（インデックス）として使用されます。
  - t := m[i]; m[i] = m[j]; m[j] = t;:
    - これは典型的な値の交換（スワップ）操作です。
    - m[i]の現在の値を一時変数tに保存します。
    - m[j]の値をm[i]にコピーします。
    - tに保存しておいた元のm[i]の値をm[j]にコピーします。
    - これにより、m[i]とm[j]の値が交換されます。

この実装は、Fisher-Yatesシャッフルアルゴリズムの「内側から外側へ」のバリアントに似ていますが、ループの範囲とランダムなインデックスの選択方法が若干異なります。しかし、結果としてすべての順列が等しい確率で生成されるという特性は維持されています。

参考にした情報源リンク

Go言語の公式ドキュメント
Fisher-Yatesシャッフルに関する一般的なアルゴリズム解説
Go言語のmap型に関するドキュメント
Go言語の初期のソースコードとコミット履歴（GitHub）

comemo