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

コミット

コミットハッシュ: 497e648e7ec0bb98e2c46e5facbe5ae3837b8312
Author: Ken Thompson ken@golang.org
Date: Tue Nov 18 19:59:56 2008 -0800

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

https://github.com/golang/go/commit/497e648e7ec0bb98e2c46e5facbe5ae3837b8312

元コミット内容

    perm is [] instead of map
    
    R=r
    OCL=19569
    CL=19569

変更の背景

このコミットは、Go言語の標準ライブラリsrc/lib/rand.go内のperm関数において、ランダムな順列（permutation）を表現するためのデータ構造をmap[int]intから[]int（スライス）に変更するものです。

変更の背景には、Go言語の設計思想と、データ構造の効率性に関する考慮があります。順列は、通常、要素の順序付けられたリストとして表現されます。例えば、0からn-1までの整数の順列は、長さnの配列（またはスライス）で、各インデックスにその位置の要素が格納される形で自然に表現できます。

初期のGo言語開発段階において、perm関数がmap[int]intを使用していたのは、おそらく柔軟性や初期の実装の容易さを考慮した結果かもしれません。しかし、順列のように密な（0からn-1までの全ての整数がキーとして存在する）マッピングの場合、ハッシュテーブルを基盤とするmapは、連続したメモリ領域に要素を格納する[]int（スライス）に比べて、メモリ使用量やアクセス速度の点で非効率になります。

この変更は、randパッケージのperm関数が生成する順列の表現を、よりGo言語のイディオムに沿った、効率的かつパフォーマンスの高いものにするための改善であると考えられます。特に、ランダムな順列の生成は、多くのアルゴリズムやシミュレーションで頻繁に利用されるため、その基盤となるデータ構造の選択は重要です。

前提知識の解説

Go言語のスライス (`[]T`)

Go言語のスライスは、同じ型の要素の可変長シーケンスを表すデータ構造です。スライスは、内部的には配列への参照、長さ、容量の3つの要素で構成されます。

参照: スライスが指し示す基底配列の先頭要素へのポインタ。
長さ (length): スライスに含まれる要素の数。len(s)で取得。
容量 (capacity): スライスの基底配列の長さ。スライスが拡張できる最大長。cap(s)で取得。

スライスは、配列の一部を「ビュー」として提供するため、非常に柔軟で効率的です。要素は連続したメモリ領域に格納されるため、インデックスによるアクセスが高速です。make([]T, length, capacity)で作成でき、append関数で要素を追加すると、必要に応じて基底配列が拡張されます。

Go言語のマップ (`map[K]V`)

Go言語のマップは、キーと値のペアを格納するハッシュテーブルの実装です。キーは一意であり、値にマッピングされます。

キー (K): 比較可能な型（整数、文字列、ポインタなど）である必要があります。
値 (V): 任意の型を取ることができます。

マップは、キーに基づいて値を高速に検索、挿入、削除するために設計されています。しかし、要素はメモリ上で連続して配置されるわけではなく、ハッシュ関数と衝突解決のメカニズムを伴うため、スライスのような連続メモリアクセスに比べてオーバーヘッドがあります。make(map[K]V)で作成します。

順列 (Permutation)

順列とは、いくつかの異なる要素を特定の順序で並べたものです。例えば、1, 2, 3の順列は (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) の6通りです。数学的には、n個の異なる要素からk個を選んで並べる順列をP(n, k)と表記します。このコミットで扱われているのは、n個の要素全てを並べる順列（n個の要素の並べ替え）であり、これはn!（nの階乗）通りの組み合わせがあります。プログラミングにおいては、0からn-1までの整数を要素とする順列は、長さnの配列やスライスで表現するのが一般的です。例えば、[0, 2, 1]は、要素0が0番目、要素2が1番目、要素1が2番目にある順列を表します。

技術的詳細

このコミットの技術的な核心は、順列の表現方法をmap[int]intから[]intに変更した点にあります。

`map[int]int`で順列を表現する場合の課題

map[int]intを使用して0からn-1までの順列を表現する場合、キーが元のインデックス、値がそのインデックスに対応する順列後の値となります。例えば、map[int]int{0:0, 1:2, 2:1}は順列[0, 2, 1]を表します。

このアプローチの課題は以下の通りです。

メモリ効率: mapはハッシュテーブルとして実装されており、各エントリ（キーと値のペア）は、ハッシュ値の計算、バケットへの格納、衝突解決のための追加のメモリオーバーヘッドを伴います。順列のようにキーが0からn-1まで密に存在する（つまり、全てのキーが存在する）場合、このオーバーヘッドは大きくなります。
アクセス速度: mapへのアクセスは、ハッシュ関数の計算と、場合によってはハッシュ衝突の解決を伴います。これは、連続したメモリ領域に格納されたスライスへのインデックスアクセス（直接メモリアドレスを計算できる）よりも遅くなる可能性があります。
イディオム: Go言語において、順序付けられた要素のコレクションは通常スライスで表現されます。mapは、キーによる高速なルックアップが必要な、疎な（一部のキーしか存在しない）データや、キーと値の関連付けが重要な場合に適しています。

`[]int`で順列を表現する場合の利点

[]intを使用して0からn-1までの順列を表現する場合、スライスのインデックスが元のインデックス、スライスの値がそのインデックスに対応する順列後の値となります。例えば、[]int{0, 2, 1}は順列[0, 2, 1]を表します。

このアプローチの利点は以下の通りです。

メモリ効率: スライスは要素を連続したメモリ領域に格納するため、mapのような追加のオーバーヘッドがありません。これにより、メモリ使用量が削減されます。
アクセス速度: スライスへのインデックスアクセスは、メモリアドレスの直接計算によって行われるため、非常に高速です。
イディオム: Go言語の標準的なデータ構造であり、順序付けられたコレクションを扱う上で自然な選択です。
初期化: new([]int, n)（Go 1.0以前の構文、現在のmake([]int, n)に相当）で直接指定された長さのスライスを効率的に初期化できます。

`new([]int, n)`について (Go 1.0以前の構文)

コミットのコードではm := new([]int, n);という記述があります。これはGo言語の非常に初期の構文であり、現在のGo言語ではmake([]int, n)に相当します。

new(T): 型Tのゼロ値へのポインタを返します。
make(T, args): スライス、マップ、チャネルといった組み込み型を初期化し、使用可能な状態にします。スライスの場合、長さと容量を指定して基底配列を割り当てます。

このコミットが行われた2008年11月時点では、Go言語はまだ開発の初期段階であり、言語仕様や標準ライブラリのAPIが頻繁に変更されていました。new([]int, n)は、当時のスライスの初期化方法の一つだったと考えられます。現在のGoでは、スライスを特定の長さで初期化するにはmakeを使用するのが正しい方法です。

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

src/lib/rand.go ファイルにおいて、以下の変更が行われました。

--- a/src/lib/rand.go
+++ b/src/lib/rand.go
@@ -14,7 +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
+// perm gives a random permutation []int
 
 const
 (
@@ -164,9 +164,9 @@ frand() float
 }
 
 export func
-perm(n int) *map[int]int
+perm(n int) *[]int
 {
-\tm := new(map[int]int);\n+\tm := new([]int, n);\n \tfor i:=0; i<n; i++ {\n \t\tm[i] = i;\n \t}\n```

## コアとなるコードの解説

このコミットでは、`src/lib/rand.go`ファイル内の`perm`関数のシグネチャと実装が変更されています。

1.  **コメントの変更**:
    ```diff
    -// perm gives a random permutation map[int]int
    +// perm gives a random permutation []int
    ```
    `perm`関数の説明コメントが更新され、戻り値の型が`map[int]int`から`[]int`に変更されたことが明示されています。これは、関数の外部インターフェースの変更を反映しています。

2.  **関数のシグネチャの変更**:
    ```diff
    -perm(n int) *map[int]int
    +perm(n int) *[]int
    ```
    `perm`関数の戻り値の型が`*map[int]int`（`map[int]int`へのポインタ）から`*[]int`（`[]int`へのポインタ）に変更されました。これにより、関数は順列をスライスとして返すようになります。

3.  **順列を格納する変数の初期化の変更**:
    ```diff
    -\tm := new(map[int]int);\n+\tm := new([]int, n);\n    ```
    これが最も重要な変更点です。
    -   変更前: `m := new(map[int]int);`
        これは、空の`map[int]int`を指すポインタを初期化しています。この時点ではマップは`nil`であり、使用する前に`make`で初期化する必要があります（ただし、この初期のGoのコードでは`new`がマップの初期化にも使われていた可能性がありますが、現在のGoではマップの初期化には`make`が必須です）。
    -   変更後: `m := new([]int, n);`
        これは、長さ`n`のスライスを指すポインタを初期化しています。Go言語の初期のバージョンでは、`new([]int, n)`は長さ`n`のスライスをゼロ値で初期化し、そのスライスへのポインタを返す動作をしていたと考えられます。現在のGoでは、`make([]int, n)`がこれに相当し、長さ`n`の`int`型スライスを生成し、各要素を`0`で初期化します。

    この変更により、`perm`関数は順列を格納するために`map`ではなく、最初から適切な長さで初期化された`[]int`を使用するようになります。

4.  **ループ内の代入**:
    ```go
    	for i:=0; i<n; i++ {
    		m[i] = i;
    	}
    ```
    このループは、変更前後で同じロジックを保持しています。`m[i] = i`という代入は、`m`が`map`である場合はキー`i`に値`i`をマッピングし、`m`がスライスである場合はインデックス`i`に値`i`を代入します。どちらの場合も、初期状態として`[0, 1, 2, ..., n-1]`という順列（恒等順列）を作成しています。その後のコード（このdiffには含まれていませんが、`rand.go`の`perm`関数全体を見れば、この初期化されたスライスをシャッフルするロジックが続くはずです）で、このスライスをランダムに並べ替えることで順列を生成します。

この変更は、`perm`関数がより効率的で、Go言語のイディオムに沿った方法で順列を生成するようにするための重要な改善です。

## 関連リンク

- Go言語公式ドキュメント: [https://go.dev/doc/](https://go.dev/doc/)
- Go言語のブログ: [https://go.dev/blog/](https://go.dev/blog/)

## 参考にした情報源リンク

- Go言語の`map`と`slice`に関する一般的な知識
- Go言語の初期の歴史と構文に関する情報（`new([]int, n)`の解釈のため）
- 順列の概念に関する一般的な数学的知識

Keyboard shortcuts

comemo