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

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

このコミットは、Go言語のsrc/lib/container/arrayパッケージにおける配列コンテナの機能拡張とリファクタリングに関するものです。具体的には、配列操作のための新しいメソッド（Slice, Cut, InsertArray, AppendArray）が追加され、既存のRemoveメソッドがDeleteにリネームされました。また、コードのファクタリングが進められ、テストが追加されています。

コミット

commit cb659ece0e9a74dd330d774552a1f26c4a4d4ee3
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Jan 28 13:32:31 2009 -0800

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

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

元コミット内容

    additions to array container:
    - added Slice, Cut, InsertArray, AppendArray
    - renamed Remove -> Delete (so we have: Insert, Delete, Cut)
    - more factoring of code
    - extra tests (could use some more)
    
    R=r,rsc
    DELTA=179  (127 added, 22 deleted, 30 changed)
    OCL=23648
    CL=23685

変更の背景

このコミットが行われた2009年1月は、Go言語がまだ一般に公開される前の初期開発段階にあたります。container/arrayパッケージは、Go言語における基本的なデータ構造の一つである動的配列（スライスに相当する概念）を実装するためのものでした。

初期のGo言語では、現在のような組み込みのスライス型が完全に成熟していなかったか、あるいはcontainerパッケージ群がより汎用的なデータ構造を提供するための実験的な位置づけであった可能性があります。このコミットの背景には、配列操作の基本的な機能（要素の挿入、削除、部分配列の取得、結合など）をより網羅的かつ効率的に提供する必要があったと考えられます。

特に、RemoveからDeleteへのリネームは、Insert, Delete, Cutという一貫性のある命名規則を確立し、APIの使いやすさと理解しやすさを向上させる意図があったと推測されます。また、コードのファクタリングとテストの追加は、コードベースの品質向上と将来的なメンテナンス性を考慮したものです。

前提知識の解説

Go言語の初期の配列とスライス

Go言語には、固定長配列と動的長配列であるスライスが存在します。このコミットが行われた時期は、Go言語のスライスが現在のような強力な組み込み型として確立される過渡期であったと考えられます。container/arrayパッケージは、おそらくスライスの概念をユーザーランドで実装し、その振る舞いを検証するためのものだったと推測されます。

  • len()とcap(): Go言語のスライスには、len()（要素数）とcap()（容量、基底配列のサイズ）という2つの重要なプロパティがあります。len()は現在スライスに含まれている要素の数を返し、cap()はスライスが参照している基底配列が保持できる最大要素数を返します。スライスが容量を超えて要素を追加しようとすると、より大きな基底配列が割り当てられ、既存の要素が新しい配列にコピーされます。
  • make(): スライスを初期化する際に使用される組み込み関数です。make([]T, length, capacity)のように使用し、指定された型T、長さlength、容量capacityを持つスライスを作成します。
  • copy(): スライス間で要素をコピーするための組み込み関数です。copy(dst, src)のように使用し、srcスライスの要素をdstスライスにコピーします。コピーされる要素数は、dstとsrcの長さの小さい方に制限されます。
  • nilへの設定とガベージコレクション (GC): Go言語はガベージコレクタを持つ言語です。スライスから要素を削除する際、その要素が参照していたオブジェクトが他のどこからも参照されなくなるように、明示的にnilを設定することが推奨される場合があります。これにより、ガベージコレクタがそのオブジェクトを回収できるようになり、メモリリークを防ぐことができます。

interface{}型

Go言語のinterface{}型は、任意の型の値を保持できる空のインターフェースです。これは、他の言語におけるObject型やAny型に似ています。container/arrayパッケージのElement interface{}は、このinterface{}型をエイリアスしたものであり、Arrayが任意の型の要素を格納できる汎用的なコンテナであることを示しています。

型アサーション

x.(T)という構文は、インターフェース型の値xが特定の型Tの基底値を持っているかどうかをチェックし、もし持っていればその基底値をT型として抽出する「型アサーション」です。このコミットのテストコードでは、a.At(i).(int)のように使用されており、At(i)メソッドが返すElement（interface{}）をint型として扱っています。

技術的詳細

このコミットの主要な変更点は、Array構造体の内部実装と、それに関連するメソッドの追加・変更です。

expand関数の導入

以前のInsertメソッドでは、配列の容量が不足した場合にその場で容量を倍増させるロジックが含まれていました。このコミットでは、この容量拡張と要素の移動（穴を開ける処理）のロジックがexpandというヘルパー関数に切り出されました。

func expand(a []Element, i, n int) []Element {
	// make sure we have enough space
	len0 := len(a);
	len1 := len0 + n;
	if len1 < cap(a) {
		// enough space - just expand
		a = a[0 : len1]
	} else {
		// not enough space - double capacity
		capb := cap(a)*2;
		if capb < len1 {
			// still not enough - use required length
			capb = len1
		}
		// capb >= len1
		b := make([]Element, len1, capb);
		copy(b, a);
		a = b
	}

	// make a hole
	for j := len0-1; j >= i ; j-- {
		a[j+n] = a[j]
	}
	return a
}
  • expand関数は、スライスaにn個の要素を位置iに挿入するために必要なスペースを確保します。
  • 現在の容量cap(a)が不足している場合、新しい容量capbを計算します。基本的には現在の容量の2倍ですが、それでも必要な長さlen1に満たない場合はlen1を使用します。
  • 新しい容量でmakeを使って新しい基底配列bを作成し、既存の要素をcopyします。
  • その後、forループを使って位置iから後ろの要素をn個分ずらし、「穴」を開けます。

このexpand関数を導入することで、Insertや新しく追加されたInsertArrayメソッドで容量拡張と要素移動のロジックを再利用できるようになり、コードの重複が削減され、保守性が向上しています。

copy関数の導入

Go言語には組み込みのcopy関数がありますが、このコミットではElement型に特化したcopyヘルパー関数が定義されています。

func copy(dst, src []Element) {
	for i := 0; i < len(src); i++ {
		dst[i] = src[i]
	}
}

これは、当時のGo言語の組み込みcopy関数の挙動や、Elementインターフェース型を扱う上での特定の要件（例えば、型アサーションなしでの要素のコピー）に対応するためのものかもしれません。しかし、現代のGo言語では組み込みのcopy関数が非常に効率的であり、このようなラッパーは通常不要です。

Array構造体の定義変更

以前はArray構造体のフィールドaがエクスポートされていましたが、このコミットで非エクスポートフィールドに変更されています。

// Before
type Array struct {
	// TODO do not export field
	a []Element
}

// After
type (
	Element interface {};
	Array struct {
		a []Element
	}
)

これは、Arrayの内部実装を隠蔽し、外部からはメソッドを通じてのみアクセスさせるという、より良いカプセル化の原則に従った変更です。

新しいメソッドの追加

  • Slice(i, j int) *Array:

    • p.a[i : j]を使って元の配列の部分スライスを作成し、その部分スライスを基に新しいArrayインスタンスを生成して返します。
    • これにより、元の配列を変更せずに部分配列を取得できるようになります。
    • New(j - i)で新しい配列を初期化し、copy(s.a, p.a[i : j])で要素をコピーしています。

  • Cut(i, j int):

    • 配列のインデックスiからj-1までの要素を削除します。
    • copy(a[i : m], a[j : n])を使って、削除対象の範囲より後ろの要素を前に詰めます。
    • 削除された要素が占めていた領域は、ガベージコレクションのためにnilで埋められます（a[k] = nil）。
    • p.a = a[0 : m]でスライスの長さを更新します。

  • InsertArray(i int, x *Array):

    • 別のArrayインスタンスxの全要素を、現在の配列の指定された位置iに挿入します。
    • expand(p.a, i, len(x.a))を呼び出して必要なスペースを確保し、copy(p.a[i : i + len(x.a)], x.a)で要素をコピーします。

  • AppendArray(x *Array):

    • InsertArrayのラッパーで、配列の末尾に別のArrayインスタンスxの全要素を追加します。
    • p.InsertArray(len(p.a), x)を呼び出します。

メソッドのリネームと変更

  • Remove(i int) -> Delete(i int):

    • RemoveメソッドがDeleteにリネームされました。機能的には同じで、指定されたインデックスiの要素を削除し、その要素を返します。
    • 内部的には、copyを使って要素を前に詰め、削除された要素をnilに設定してGCを助けます。
    • Pop()メソッドもp.Remove(len(p.a) - 1)からp.Delete(len(p.a) - 1)に更新されています。

  • Insert(i int, x Element):

    • 以前はInsertメソッド内にあった容量拡張と要素移動のロジックがexpand関数に切り出されたため、Insertメソッド自体は非常に簡潔になりました。
    • p.a = expand(p.a, i, 1)でスペースを確保し、p.a[i] = xで要素を挿入します。

テストの変更

  • TestInsertRemoveClearがTestInsertDeleteClearにリネームされ、Removeの呼び出しがDeleteに更新されました。
  • 新しいメソッドSliceとInsertArrayのテストが追加されました。特にTestInsertArrayでは、様々なシナリオ（空の配列の挿入、中間への挿入、容量を超える挿入など）が検証されています。
  • テストヘルパー関数Valがvalにリネームされ、非エクスポートになりました。
  • verify_slice, verify_pattern, make_arrayといった新しいテストヘルパー関数が追加され、テストコードの可読性と再利用性が向上しています。

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

src/lib/container/array/array.go

  • ElementとArrayの型定義が変更され、Arrayの内部フィールドaが非エクスポートになった。
  • copyヘルパー関数が追加された。
  • expandヘルパー関数が追加された。
  • Insertメソッドの内部実装がexpandを使用するように変更された。
  • RemoveメソッドがDeleteにリネームされ、実装が変更された。
  • InsertArrayメソッドが追加された。
  • Cutメソッドが追加された。
  • Sliceメソッドが追加された。
  • PopメソッドがDeleteを使用するように変更された。
  • AppendArrayメソッドが追加された。

src/lib/container/array/array_test.go

  • TestInsertRemoveClearがTestInsertDeleteClearにリネームされ、Removeの呼び出しがDeleteに更新された。
  • valヘルパー関数が追加され、Valが削除された。
  • verify_slice, verify_pattern, make_arrayヘルパー関数が追加された。
  • TestInsertArrayテスト関数が追加された。

src/lib/container/array/intarray.go

  • RemoveメソッドがDeleteにリネームされ、Array.Deleteを呼び出すように変更された。

test/vectors.go

  • v.Remove(10)の呼び出しがv.Delete(10)に更新された。

コアとなるコードの解説

expand関数

この関数は、Goのスライスが動的にサイズ変更される際の基本的なメカニズムを実装しています。

  1. 容量の確認と拡張:

    • len0は現在のスライスの長さ、len1は新しいスライスの目標長さ（現在の長さ + 挿入する要素数）です。
    • len1 < cap(a)の場合、現在の基底配列に十分な容量があるため、スライスの長さをlen1に拡張するだけで済みます（a = a[0 : len1]）。これは、スライスが基底配列のビューであることを利用した効率的な操作です。
    • 容量が不足している場合（len1 >= cap(a)）、新しい基底配列を割り当てる必要があります。
      • 新しい容量capbは、現在の容量の2倍を試みます。これは一般的な動的配列の実装で採用される戦略で、再割り当ての頻度を減らし、償却定数時間での追加操作を可能にします。
      • もし2倍してもlen1に満たない場合は、最低限必要なlen1を容量とします。
      • make([]Element, len1, capb)で新しいスライスbを作成し、copy(b, a)で既存の要素を新しいスライスにコピーします。
      • 最後に、a = bで元のスライス変数を新しいスライスに置き換えます。

  2. 穴を開ける:

    • for j := len0-1; j >= i ; j-- { a[j+n] = a[j] }のループは、挿入位置iから後ろの要素をn個分、後方にずらします。これにより、iからi+n-1までの位置に新しい要素を挿入するための「穴」が作成されます。ループが逆順なのは、要素を上書きせずに正しく移動させるためです。

Array.Insert(i int, x Element)

このメソッドは、指定された位置iに単一の要素xを挿入します。

  • p.a = expand(p.a, i, 1): expand関数を呼び出し、1つの要素を挿入するためのスペースを確保し、既存の要素を移動させます。
  • p.a[i] = x: 確保された位置iに新しい要素xを代入します。

Array.Delete(i int) Element

このメソッドは、指定された位置iの要素を削除し、削除された要素を返します。

  • x := a[i]: 削除される要素を一時変数xに保存します。
  • copy(a[i : n-1], a[i+1 : n]): 削除対象の要素の次の要素から末尾までの範囲を、削除対象の要素の位置から1つ前にコピーします。これにより、削除対象の要素が上書きされ、配列が詰まります。
  • a[n-1] = nil: 削除された要素が元々あった位置（配列の末尾に移動した位置）をnilに設定します。これは、その要素が参照していたオブジェクトがガベージコレクタによって回収されるようにするためです。
  • p.a = a[0 : n-1]: スライスの長さを1つ減らします。

Array.Cut(i, j int)

このメソッドは、指定された範囲[i, j)の要素を削除します。

  • m := n - (j - i): 削除後の新しい配列の長さを計算します。
  • copy(a[i : m], a[j : n]): 削除対象の範囲[i, j)の直後にある要素a[j : n]を、削除対象の範囲の開始位置iにコピーします。これにより、削除対象の要素が上書きされ、配列が詰まります。
  • for k := m; k < n; k++ { a[k] = nil }: 削除された要素が元々占めていた領域（配列の末尾に移動した部分）をnilで埋め、GCを助けます。
  • p.a = a[0 : m]: スライスの長さを新しい長さmに更新します。

Array.Slice(i, j int) *Array

このメソッドは、元の配列の部分スライスを新しいArrayインスタンスとして返します。

  • s := New(j - i): 新しいArrayインスタンスsを作成します。その初期容量は、部分スライスの長さj - iです。
  • copy(s.a, p.a[i : j]): 元の配列p.aの[i, j)範囲の要素を、新しく作成されたs.aにコピーします。これにより、新しいArrayは元の配列の独立したコピーとなります。

Array.InsertArray(i int, x *Array)

このメソッドは、別のArrayインスタンスxの全要素を、現在の配列の指定された位置iに挿入します。

  • p.a = expand(p.a, i, len(x.a)): expand関数を呼び出し、xの要素数分のスペースを確保し、既存の要素を移動させます。
  • copy(p.a[i : i + len(x.a)], x.a): xの要素を、確保された位置iからコピーします。

関連リンク

参考にした情報源リンク

  • Go言語の初期開発に関する情報（Goのブログやメーリングリストのアーカイブなど）
  • Go言語のスライスに関する一般的な解説記事
  • 動的配列の実装に関するデータ構造とアルゴリズムの知識