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

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

このコミットは、Go言語の標準ライブラリである container/heap パッケージの例を改善し、より分かりやすくするための変更です。具体的には、既存の example_test.go ファイルを分割し、シンプルな整数ヒープの例 (example_intheap_test.go) を追加するとともに、より複雑な優先度キューの例 (example_pq_test.go) を修正しています。

コミット

commit 0e74f04accf82abb075a4d7a908e0b726d9752dd
Author: Caleb Spare <cespare@gmail.com>
Date:   Wed Jan 30 23:14:29 2013 -0800

    container/heap: split example into two
    
    This adds a simple IntHeap example, and modifies the more complex
    PriorityQueue example to make use of the index field it maintains.
    
    Fixes #4331.
    
    R=rsc, adg
    CC=golang-dev
    https://golang.org/cl/7068048

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

https://github.com/golang/go/commit/0e74f04accf82abb075a4d7a908e0b726d9752dd

元コミット内容

container/heap: split example into two

このコミットは、container/heap パッケージの例を2つに分割します。 これにより、シンプルな IntHeap の例が追加され、より複雑な PriorityQueue の例は、それが保持する index フィールドを利用するように修正されます。 Issue #4331 を修正します。

変更の背景

この変更の背景には、Go言語の container/heap パッケージの利用例をより明確にし、学習しやすくするという目的があります。元の example_test.go は、優先度キューという比較的複雑なデータ構造の例のみを含んでいました。これは container/heap パッケージの強力な機能を示すものでしたが、ヒープの基本的な概念や heap.Interface の実装方法を理解しようとする初心者にとっては、少し敷居が高いものでした。

Issue #4331 は、この例の複雑さに関するものであったと推測されます。シンプルな整数ヒープの例を追加することで、ユーザーは container/heap パッケージがどのように機能するかを、より基本的なレベルから段階的に理解できるようになります。また、既存の優先度キューの例を修正し、index フィールドをより効果的に利用するようにすることで、その実装の意図と効率性が向上しています。これにより、heap.Remove や heap.Push といった操作が、優先度キューの文脈でどのように機能するかがより明確になります。

前提知識の解説

このコミットを理解するためには、以下の概念に関する前提知識があると役立ちます。

1. ヒープ (Heap)

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

  • 最小ヒープ (Min-Heap): 親ノードの値がその子ノードの値よりも常に小さいか等しい。したがって、ルートノードが常に最小値を持つ。
  • 最大ヒープ (Max-Heap): 親ノードの値がその子ノードの値よりも常に大きいか等しい。したがって、ルートノードが常に最大値を持つ。

ヒープは通常、配列で実装され、ツリー構造は配列のインデックスによって表現されます。これにより、効率的な挿入 (Push) と削除 (Pop) 操作が可能になります。

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

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

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

Go言語の container/heap パッケージは、汎用的なヒープ操作を提供します。このパッケージ自体は具体的なヒープデータ構造を実装しているわけではありません。その代わりに、heap.Interface というインターフェースを定義しており、このインターフェースを実装する任意の型をヒープとして扱うことができます。

heap.Interface は以下のメソッドを要求します。

  • Len() int: ヒープ内の要素数を返します。
  • Less(i, j int) bool: i 番目の要素が j 番目の要素よりも優先度が高い（小さい）場合に true を返します。最小ヒープの場合は h[i] < h[j]、最大ヒープの場合は h[i] > h[j] となります。
  • Swap(i, j int): i 番目の要素と j 番目の要素を交換します。
  • Push(x interface{}): ヒープに要素 x を追加します。
  • Pop() interface{}: ヒープから最も優先度の高い要素（ルート要素）を削除し、返します。

container/heap パッケージは、heap.Init(), heap.Push(), heap.Pop(), heap.Remove(), heap.Fix() といった関数を提供し、これらは heap.Interface を実装した型に対してヒープ操作を実行します。

4. Go言語のテストと例 (Examples)

Go言語では、_test.go ファイル内に Example_FunctionName() のような形式の関数を記述することで、コードの利用例を示すことができます。これらの例は、通常のテストと同様に go test コマンドで実行され、出力がコメント (// Output:) と一致するかどうかが検証されます。これは、ドキュメントとテストの両方の役割を果たす非常に便利な機能です。

技術的詳細

このコミットの技術的詳細は、主に container/heap パッケージの利用方法と、その例の構造化に焦点を当てています。

1. heap.Interface の実装

container/heap パッケージを使用する上で最も重要なのは、カスタム型が heap.Interface を正しく実装することです。

  • IntHeap の場合: []int 型をベースに、Len, Less, Swap, Push, Pop メソッドを実装しています。Less メソッドが h[i] < h[j] と定義されているため、これは最小ヒープとして機能します。Push と Pop は、スライスの長さを変更するため、ポインタレシーバ (*IntHeap) を使用しています。
  • PriorityQueue の場合: []*Item 型をベースに heap.Interface を実装しています。Item 構造体は value と priority に加えて index フィールドを持ちます。この index フィールドは、ヒープ内でのアイテムの現在の位置を追跡するために使用されます。これは、heap.Remove や heap.Fix のような操作で特定のアイテムを効率的に見つけて更新するために不可欠です。Less メソッドは pq[i].priority < pq[j].priority と定義されており、これも最小ヒープとして機能します（優先度が小さいほど「高い」と見なされる）。

2. index フィールドの利用

PriorityQueue の例では、Item 構造体に index フィールドが追加され、このフィールドが Push および Pop 操作中に更新されます。

  • Push 時: 新しいアイテムがヒープに追加される際、その index フィールドに現在のスライス長 (n) が設定されます。
  • Pop 時: アイテムがヒープから削除される際、その index フィールドが -1 に設定されます。これは、そのアイテムがもはやヒープ内に存在しないことを示すための安全策です。

この index フィールドは、update メソッドで特に重要になります。update メソッドは、特定のアイテムの優先度や値を変更する際に、そのアイテムの現在の index を利用して heap.Remove を呼び出し、ヒープから一度削除し、新しい優先度で再度 heap.Push することでヒープのプロパティを維持します。これにより、ヒープ全体を再構築することなく、特定の要素を効率的に更新できます。

3. 例の分割と命名規則

Go言語のテストパッケージでは、Example_FunctionName() のような命名規則に従うことで、go doc コマンドでドキュメントとして表示される例を生成できます。

  • example_intheap_test.go に追加された Example_intHeap() は、シンプルな整数ヒープの利用方法を示します。
  • example_test.go から example_pq_test.go にリネームされたファイル内の Example_priorityQueue() は、より複雑な優先度キューの利用方法を示します。

この分割により、ユーザーはまず IntHeap のような基本的な例でヒープの概念を把握し、その後 PriorityQueue のようなより高度な例に進むことができます。

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

このコミットでは、以下の3つのファイルが変更されています。

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

    • シンプルな整数ヒープ (IntHeap) の定義と、それを用いた Example_intHeap() 関数が追加されています。
    • IntHeap は []int 型をベースとし、heap.Interface を実装しています。
    • Example_intHeap() では、heap.Init でヒープを初期化し、heap.Push で要素を追加し、heap.Pop で要素を優先度順に取り出す様子が示されています。

  2. src/pkg/container/heap/{example_test.go => example_pq_test.go} (ファイル名変更と内容修正)

    • 元の example_test.go が example_pq_test.go にリネームされました。
    • PriorityQueue の Push メソッドから、コメント // Push and Pop use pointer receivers because they modify the slice's length, // not just its contents. が削除されました。これは IntHeap の例に移動したためです。
    • PriorityQueue の Pop メソッドで、スライス操作の変数名が a から old に変更されました。
    • update メソッドのシグネチャが変更され、item *Item を引数として受け取るようになりました。これにより、特定のアイテムを直接更新できるようになりました。
      • 変更前: func (pq *PriorityQueue) update(value string, priority int)
      • 変更後: func (pq *PriorityQueue) update(item *Item, value string, priority int)
    • changePriority メソッドが削除され、その機能は update メソッドに統合されました。
    • Example() 関数が Example_priorityQueue() にリネームされ、その内容が大幅に簡素化・明確化されました。
      • ランダムな優先度と値の配列を使用する代わりに、map[string]int を使用して初期アイテムを定義。
      • 新しいアイテム (orange) を挿入し、その優先度を update メソッドで変更する例が追加されました。
      • 出力がより簡潔になり、優先度と値が 05:orange 04:pear 03:banana 02:apple のように表示されるようになりました。

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

    • heap パッケージのドキュメンテーションコメントが修正されました。
    • // implementation; the file example_test.go has the complete source. から // implementation; the file example_pq_test.go has the complete source. に変更され、優先度キューの例のファイル名変更が反映されました。

コアとなるコードの解説

src/pkg/container/heap/example_intheap_test.go

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 最小ヒープ
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func Example_intHeap() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h) // ヒープの初期化
	heap.Push(h, 3) // 要素の追加
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h)) // 優先度順（最小値から）の取り出し
	}
	// Output: 1 2 3 5
}

このコードは、container/heap パッケージを使って最もシンプルな整数ヒープを実装する方法を示しています。IntHeap 型は []int のエイリアスであり、heap.Interface の5つのメソッド (Len, Less, Swap, Push, Pop) を実装しています。Less メソッドが h[i] < h[j] と定義されているため、これは最小ヒープとして機能し、Pop 操作は常に最小の要素を返します。Example_intHeap 関数は、ヒープの初期化、要素の追加、そして優先度順の取り出しという一連の操作を示しており、その出力が期待通りであることを検証しています。

src/pkg/container/heap/example_pq_test.go

// Item represents an item in the priority queue.
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 update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

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

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 // 優先度が小さいほど「高い」と見なす（最小ヒープ）
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i // index フィールドの更新
	pq[j].index = j // index フィールドの更新
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n // index フィールドの設定
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety // ヒープから削除されたことを示す
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	heap.Remove(pq, item.index) // index を使ってアイテムを削除
	item.value = value
	item.priority = priority
	heap.Push(pq, item) // 新しい優先度で再挿入
}

func Example_priorityQueue() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue and put the items in it.
	pq := &PriorityQueue{}
	heap.Init(pq)
	for value, priority := range items {
		item := &Item{
			value:    value,
			priority: priority,
		}
		heap.Push(pq, item)
	}

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(pq, item)
	pq.update(item, item.value, 5) // アイテムの優先度を更新

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := heap.Pop(pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
	// Output:
	// 05:orange 04:pear 03:banana 02:apple
}

このコードは、container/heap パッケージを使用してより複雑な優先度キューを実装する方法を示しています。Item 構造体は値と優先度に加えて index フィールドを持ち、これがヒープ内でのアイテムの位置を追跡するために重要です。Swap メソッドでは、要素が交換されるたびにその index フィールドも更新されます。

特に注目すべきは update メソッドです。このメソッドは、heap.Remove 関数と item.index を組み合わせて、ヒープ内の特定のアイテムを効率的に更新する方法を示しています。まず heap.Remove(pq, item.index) で指定されたアイテムをヒープから削除し、その後、そのアイテムの優先度と値を更新し、heap.Push(pq, item) でヒープに再挿入します。これにより、ヒープのプロパティが維持され、アイテムが新しい優先度に基づいて正しい位置に配置されます。

Example_priorityQueue 関数は、複数のアイテムを優先度キューに追加し、その後、特定のアイテムの優先度を動的に変更するシナリオを示しています。最終的に、Pop 操作によってアイテムが優先度順に取り出される様子が示されており、update 操作が正しく機能していることが確認できます。

関連リンク

参考にした情報源リンク