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

このコミットは、Go言語の標準ライブラリである container/heap パッケージに、具体的な使用例を追加するものです。特に、godoc が例を適切に表示するための機能がまだ不十分であった時期に、将来的な godoc の改善を見越して「例の例」を提供することを目的としています。これにより、ヒープインターフェースを使用して優先度キューを実装する方法が示されています。

コミット

commit 44fa114dc6493d6baeae5661b7030ab1e1289ead
Author: Rob Pike <r@golang.org>
Date:   Fri Feb 10 10:07:55 2012 +1100

    container/heap: add example
    godoc doesn't have the fu to present the example well, but this gives
    us an example of an example to develop example fu.
    
    Fixes #2840.
    
    R=golang-dev, gri
    CC=golang-dev
    https://golang.org/cl/5645063

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

https://github.com/golang/go/commit/44fa114dc6493d6baeae5661b7030ab1e1289ead

元コミット内容

container/heap パッケージに例を追加しました。 godoc は例をうまく表示する機能がまだありませんが、これは将来の godoc の例表示機能開発のための「例の例」を提供します。

Issue #2840 を修正します。

レビュー担当者: golang-dev, gri CC: golang-dev 変更リスト: https://golang.org/cl/5645063

変更の背景

このコミットの主な背景は、Go言語のドキュメンテーションツールである godoc が、パッケージの使用例をより効果的に表示するための機能が不足していた点にあります。コミットメッセージにある「godoc doesn't have the fu to present the example well, but this gives us an example of an example to develop example fu.」という記述は、当時の godoc の限界を認識しつつも、将来的な機能改善を見越して、どのように例を記述すべきかを示す「模範的な例」を導入しようとする意図を示しています。

また、「Fixes #2840」とあるように、この変更はGoのIssue 2840に対応しています。Issue 2840は「container/heap: add example」というタイトルで、container/heap パッケージに具体的な使用例を追加することを求めるものでした。当時の container/heap パッケージは、ヒープインターフェースの定義は提供していましたが、それをどのように利用して優先度キューのようなデータ構造を構築するかの具体的なコード例が不足していました。これにより、ユーザーがパッケージを理解し、利用する上での障壁となっていました。

このコミットは、これらの課題を解決するために、container/heap パッケージの利用方法を具体的に示す優先度キューの実装例を example_test.go として追加しました。これにより、ユーザーはヒープインターフェースの概念をより深く理解し、自身のアプリケーションで優先度キューを効率的に実装するための具体的な指針を得られるようになりました。

前提知識の解説

1. ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、特定のヒーププロパティを満たします。ヒーププロパティには主に2種類あります。

• 最大ヒープ (Max-Heap): 親ノードの値がその子ノードの値よりも常に大きいか等しい。
• 最小ヒープ (Min-Heap): 親ノードの値がその子ノードの値よりも常に小さいか等しい。

ヒープは通常、配列で実装され、ツリー構造を効率的に表現します。ヒープの主な操作には、要素の挿入 (Push)、最大/最小要素の削除 (Pop)、最大/最小要素の参照 (Peek) などがあります。ヒープは、優先度キューの実装によく用いられます。

2. 優先度キュー (Priority Queue)

優先度キューは、各要素に「優先度」が割り当てられた抽象データ型です。通常のキューとは異なり、要素が追加された順序ではなく、その優先度に基づいて要素が取り出されます。最も優先度の高い要素が最初に取り出されます。ヒープは、優先度キューを効率的に実装するための一般的なデータ構造です。

3. Go言語の container/heap パッケージ

Go言語の標準ライブラリ container/heap パッケージは、ヒープデータ構造そのものを直接提供するわけではありません。代わりに、任意のコレクション型がヒーププロパティを満たすようにするための汎用的なインターフェース heap.Interface と、そのインターフェースを実装した型に対してヒープ操作（Push, Pop, Fix, Remove, Init）を提供する関数群を提供します。

heap.Interface は以下のメソッドを定義しています。

• Len() int: コレクションの要素数を返します。
• Less(i, j int) bool: i 番目の要素が j 番目の要素よりも優先度が低い（または小さい）場合に true を返します。最小ヒープの場合は a[i] < a[j]、最大ヒープの場合は a[i] > a[j] となります。
• Swap(i, j int): i 番目の要素と j 番目の要素を入れ替えます。

このインターフェースを実装することで、ユーザーは任意のGoのスライス型をヒープとして扱うことができ、container/heap パッケージの汎用関数を利用してヒープ操作を行うことができます。

4. godoc と Example Functions

godoc はGo言語のドキュメンテーションツールであり、Goのソースコードから直接ドキュメントを生成します。Goのパッケージや関数のドキュメントは、コードのコメントとして記述されます。

godoc は、Example というプレフィックスを持つ関数を特別な方法で扱います。これらの関数は、パッケージや型の使用例を示すために書かれ、godoc によって自動的に実行され、その出力がドキュメントに表示されます。これにより、ユーザーはコードの動作を実際に確認しながらドキュメントを読むことができます。

このコミットが作成された時点では、godoc のExample関数の表示機能はまだ発展途上でしたが、将来的にこの機能が強化されることを見越して、適切なExample関数の書き方を示す目的も含まれていました。

技術的詳細

このコミットでは、container/heap パッケージの利用例として、優先度キューの実装が src/pkg/container/heap/example_test.go に追加されています。

1. Item 構造体

優先度キューに格納される各要素を表す構造体です。

type Item struct {
	value    string // The value of the item; arbitrary.
	priority int    // The priority of the item in the queue.
	// The index is needed by changePriority and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

• value: 任意の値を保持するためのフィールド（ここでは文字列）。
• priority: アイテムの優先度を示す整数値。この値に基づいてキューからの取り出し順序が決まります。
• index: ヒープ内のアイテムの現在のインデックス。これは heap.Interface のメソッドによって内部的に管理され、特に heap.Remove や heap.Fix のような操作で特定のアイテムの優先度を変更する際に必要となります。

2. PriorityQueue 型

heap.Interface を実装するカスタム型です。Item へのポインタのスライスとして定義されています。

type PriorityQueue []*Item

この型が heap.Interface の以下のメソッドを実装します。

• Len() int:

  func (pq PriorityQueue) Len() int { return len(pq) }
  

  スライスの長さを返します。

• Less(i, j int) bool:

  func (pq PriorityQueue) Less(i, j int) bool {
  	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
  	return pq[i].priority > pq[j].priority
  }
  

  この実装では、pq[i].priority > pq[j].priority とすることで、優先度が高い（数値が大きい）アイテムほど「小さい」とみなされ、最大ヒープとして機能するようにしています。これにより、heap.Pop は常に最も優先度の高いアイテム（priorityが最大のもの）を返します。

• Swap(i, j int):

  func (pq PriorityQueue) Swap(i, j int) {
  	pq[i], pq[j] = pq[j], pq[i]
  	pq[i].index = i
  	pq[j].index = j
  }
  

  スライス内の2つのアイテムを交換し、同時にそれぞれの index フィールドも更新します。この index の更新は、heap.Remove や heap.Fix のような操作でアイテムを効率的に見つけるために重要です。

• Push(x interface{}):

  func (pq *PriorityQueue) Push(x interface{}) {
  	a := *pq
  	n := len(a)
  	a = a[0 : n+1]
  	item := x.(*Item)
  	item.index = n
  	a[n] = item
  	*pq = a
  }
  

  heap.Push 関数によって呼び出され、新しいアイテムをヒープの末尾に追加します。ポインタレシーバ (*PriorityQueue) を使用しているのは、スライスの長さが変更されるためです。追加されたアイテムの index フィールドも設定されます。

• Pop() interface{}:

  func (pq *PriorityQueue) Pop() interface{} {
  	a := *pq
  	n := len(a)
  	item := a[n-1]
  	item.index = -1 // for safety
  	*pq = a[0 : n-1]
  	return item
  }
  

  heap.Pop 関数によって呼び出され、ヒープの末尾からアイテムを取り除きます。取り除かれたアイテムの index は安全のために -1 に設定されます。こちらもポインタレシーバを使用しています。

3. ExampleInterface() 関数

この関数は、container/heap パッケージと PriorityQueue の具体的な使用方法を示す godoc のExample関数です。

func ExampleInterface() {
	// ... (ItemとPriorityQueueの定義は省略)

	const nItem = 10
	// Random priorities for the items (a permutation of 0..9, times 11)).
	priorities := [nItem]int{
		77, 22, 44, 55, 11, 88, 33, 99, 00, 66,
	}
	values := [nItem]string{
		"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
	}
	// Create a priority queue and put some items in it.
	pq := make(PriorityQueue, 0, nItem)
	for i := 0; i < cap(pq); i++ {
		item := &Item{
			value:    values[i],
			priority: priorities[i],
		}
		heap.Push(&pq, item) // heap.Pushを呼び出す
	}
	// Take the items out; should arrive in decreasing priority order.
	// For example, the highest priority (99) is the seventh item, so output starts with 99:"seven".
	for i := 0; i < nItem; i++ {
		item := heap.Pop(&pq).(*Item) // heap.Popを呼び出す
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
	// Output:
	// 99:seven 88:five 77:zero 66:nine 55:three 44:two 33:six 22:one 11:four 00:eight
}

この関数は、ランダムな優先度と値を持つ Item を作成し、それらを heap.Push を使って PriorityQueue に追加します。その後、heap.Pop を使ってアイテムをキューから取り出し、その順序が優先度に基づいて降順になっていることを示します。// Output: コメントは、godoc がこのExample関数を実行した際の期待される出力を示しており、ドキュメントに表示されます。

4. update および changePriority メソッド

これらは ExampleInterface 関数では直接使用されませんが、優先度キューの一般的な操作として、アイテムの優先度や値を更新する方法を示しています。

• update(value string, priority int): 最も優先度の高いアイテムを取り出し、その値と優先度を更新してから、再度ヒープに戻す例。
• changePriority(item *Item, priority int): 特定のアイテムの優先度を変更する例。これには heap.Remove と heap.Push を組み合わせて使用します。item.index がここで重要な役割を果たします。

5. src/pkg/container/heap/heap.go の変更

heap.go ファイルでは、コメントが一部修正されています。

--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -6,10 +6,11 @@
 // heap.Interface. A heap is a tree with the property that each node is the
 // highest-valued node in its subtree.\n //\n-// A heap is a common way to impement a priority queue. To build a priority\n+// A heap is a common way to implement a priority queue. To build a priority\n // queue, implement the Heap interface with the (negative) priority as the\n // ordering for the Less method, so Push adds items while Pop removes the\n-// highest-priority item from the queue.\n+// highest-priority item from the queue. The Examples include such an\n+// implementation; the file example_test.go has the complete source.\n //\n package heap

• impement が implement に修正されています（typo fix）。
• 優先度キューの実装に関する説明に、「The Examples include such an implementation; the file example_test.go has the complete source.」という文が追加されています。これは、新しく追加された example_test.go に優先度キューの完全な実装例があることを明示的に示しています。

これらの変更により、container/heap パッケージのドキュメントがより分かりやすくなり、ユーザーがヒープインターフェースを使って優先度キューを実装する際の具体的な手引きが提供されるようになりました。

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

1. src/pkg/container/heap/example_test.go (新規追加)

このファイル全体が新規追加されています。 主な内容は以下の通りです。

• Item 構造体の定義
• PriorityQueue 型の定義と、heap.Interface を実装する Len, Less, Swap, Push, Pop メソッドの実装
• ExampleInterface() 関数による優先度キューの具体的な使用例
• update および changePriority メソッドによる、ヒープ内のアイテムの更新・優先度変更の例

2. src/pkg/container/heap/heap.go (コメント修正)

heap.go ファイルのコメントが2箇所変更されています。

• impement -> implement (typo修正)
• 優先度キューの実装に関する説明に、example_test.go に完全なソースコードがあることを示す記述が追加されています。

コアとなるコードの解説

src/pkg/container/heap/example_test.go

このファイルは、container/heap パッケージの最も重要な変更点であり、その利用方法を具体的に示すものです。

1. Item 構造体: 優先度キューに格納されるデータの最小単位を定義します。value は実際のデータ、priority はそのデータの優先度、index はヒープ内部での位置を追跡するために使われます。特に index は、heap.Remove や heap.Fix のような操作で特定の要素を効率的に操作するために不可欠です。

2. PriorityQueue 型と heap.Interface の実装:

   • PriorityQueue は []*Item として定義され、Goのスライスを基盤としています。
   • Len(): スライスの長さを返すことで、ヒープの要素数を提供します。
   • Less(i, j int): ここが優先度キューの挙動を決定する重要な部分です。pq[i].priority > pq[j].priority とすることで、数値が大きい優先度を「より高い優先度」とみなし、heap.Pop が常に最も優先度の高い（数値が最大の）アイテムを取り出すようにします。これは、container/heap がデフォルトで最小ヒープのセマンティクスを持つため、最大ヒープのように振る舞わせるための工夫です。
   • Swap(i, j int): 要素の交換と同時に、Item 構造体内の index フィールドも更新します。これにより、ヒープ操作中に各アイテムの正確な位置が常に反映され、後続の操作（例: changePriority）でアイテムを効率的に見つけることができます。
   • Push(x interface{}) と Pop() interface{}: これらは heap.Push および heap.Pop 関数から呼び出される内部的なヘルパーメソッドです。スライスの長さを変更するため、ポインタレシーバ (*PriorityQueue) を使用しています。Pop では、取り出されたアイテムの index を -1 に設定することで、そのアイテムがもはやヒープの一部ではないことを示し、安全性を高めています。

3. ExampleInterface() 関数:

   • この関数は、container/heap パッケージの Push と Pop 関数を実際に使用して、優先度キューがどのように機能するかを示しています。
   • heap.Push(&pq, item): 新しいアイテムをヒープに追加し、ヒーププロパティを維持します。
   • heap.Pop(&pq).(*Item): 最も優先度の高いアイテム（この例では優先度数値が最大のアイテム）をヒープから取り出し、ヒーププロパティを再構築します。
   • // Output: コメントは、godoc がこの例を実行した際の期待される出力を定義しており、ドキュメントの品質と信頼性を高めます。

4. update および changePriority メソッド:

   • これらは ExampleInterface では直接使われませんが、ヒープのより高度な操作、特に既存のアイテムの優先度を変更する方法を示しています。
   • changePriority では、heap.Remove で一度ヒープからアイテムを削除し、優先度を変更した後に heap.Push で再度追加するというパターンが示されており、index フィールドの重要性が強調されています。

src/pkg/container/heap/heap.go

このファイルへの変更は、主にドキュメンテーションの改善です。

• タイポの修正 (impement -> implement) は、コードの品質と可読性を向上させます。
• 「The Examples include such an implementation; the file example_test.go has the complete source.」というコメントの追加は、ユーザーが優先度キューの実装例を探す際に、新しく追加された example_test.go を参照するように誘導し、ドキュメントの利便性を高めます。

これらの変更は、container/heap パッケージの使いやすさを大幅に向上させ、Go言語のドキュメンテーション文化におけるExample関数の重要性を示す初期のステップとなりました。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/44fa114dc6493d6baeae5661b7030ab1e1289ead
• Go Issue 2840: https://github.com/golang/go/issues/2840
• Gerrit Change-Id: https://golang.org/cl/5645063

参考にした情報源リンク

• Go言語 container/heap パッケージ公式ドキュメント: https://pkg.go.dev/container/heap
• Go言語 godoc コマンドについて: https://pkg.go.dev/cmd/godoc
• Go言語のExample関数について (Go公式ブログ): https://go.dev/blog/examples
• ヒープ (データ構造) - Wikipedia: https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)
• 優先度付きキュー - Wikipedia: https://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC