はじめに

Goにcontainerパッケージというものがあったというのを最近知りました。結構面白いなと思い書いてみました。予め申し上げておくと個人的な備忘録用に書いているので中身は薄めです。

containerパッケージには下記のデータ構造を扱える機能が存在します。

heap (ヒープソート)
list (Linked List)
ring (Circular Linked List ※末尾の次は先頭のLinked List)

ヒープソートを中心に見ていきたいと思います。

ヒープソートとは

ヒープソート

一般的に一番ポピュラーなソートアルゴリズムはクィックソートであるがデータの中身による計算量の変化量が大聞くなる可能性がある。ヒープソートは平均的にはクィックソート遅いがデータにより計算量の変化が少ない
プライオリティのあるキューイングに使用される

どんな思想でつくられたか？

Russ Coxさんが書かれた別の趣旨の記事からの引用ですが

For example, container/heap provides heap-maintenance algorithms as ordinary functions that operate on a heap.Interface, making them applicable to any backing storage, not just a slice of values. This can be very powerful.

At the same time, most programmers who want a priority queue don’t want to implement the underlying storage for it and then invoke the heap algorithms. They would prefer to let the implementation manage its own array, but Go does not permit expressing that in a type-safe way. The closest one can come is to make a priority queue of interface{} values and use type assertions after fetching each element. (The standard container/list and container/ring implementations take this approach.)

数値などの値スライスだけでなく、(heap.Interfaceを継承する)任意の型にて使用可能
ストレージ不要でプライオリティキューを使用できる
フェッチ(heapで言えばPop()メソッド)してから型変換を行う

使用例

// 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
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h)
    heap.Push(h, 3)
    fmt.Printf("minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
    // Output:
    // minimum: 1
    // 1 2 3 5
}

参照

プライオリティアイテムの場合はこちら

内部

https://github.com/golang/go/blob/master/src/container/heap/heap.go

要素(heap.Interface)

例題からもわかるように扱う要素はheap.Interfaceを継承している必要があります。 heap.Interfaceはさらにsort.Interfaceが埋め込まれています。

// heap.Interface
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

// sort.Interface
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

ヒープソート アルゴリズム

ヒープソートのアルゴリズムはプライベートファンクションとして定義されています。

func up(h Interface, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}

func down(h Interface, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2  // right child
        }
        if !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        i = j
    }
    return i > i0
}

要素の操作

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
    // heapify
    n := h.Len()
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
    h.Push(x)
    up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) interface{} {
    n := h.Len() - 1
    h.Swap(0, n)
    down(h, 0, n)
    return h.Pop()
}

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1
    if n != i {
        h.Swap(i, n)
        if !down(h, i, n) {
            up(h, i)
        }
    }
    return h.Pop()
}

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

最後に

heapだけでなくlist, ringも一度見ておくといいかと思います。どちらもフェッチ後に型変換を行うことでどんな型でも使用できます。

GoではこのようにInterfaceで引数の間口を広げてしまうソースはあまり好まれません。なので上記のRuss Coxさんの記事ではGenericの有効例としてあげられているのだと思います。

muroonのブログ

Goのcontainerパッケージを見る