goでmapのキーをソートする

結論：配列用意してコピー

試しにreflectパッケージを利用してキーを取り出してみましたが、キーの型がreflect.Valueになってしまい激遅ですちょっと遅い。

キーソートに限らずmapのカスタムソートはよく行うのでsortパッケージにはもっと頑張って欲しいです。ジェネリクスが導入されると大分変わるのかな・・・
やはりソート済みmapは追加されないんでしょうか。

でもやっぱりループ回していっこずつ値を追加するのは効率悪い気がするんだよなあ・・・

訂正: メモリ不足で不当に重くなってたみたい。
ついでにmapのkeyをランダムにして毎回初期化するようにし、
かつ全ての値をスキャンするというユースケースに変更しました。
まあでも倍くらいは遅い。

% go test sort_test.go -test.bench=".*"
testing: warning: no tests to run
PASS
BenchmarkSortByInterface    2000000000           0.04 ns/op
BenchmarkSortByBuiltin  2000000000           0.02 ns/op
BenchmarkSortByHeap 2000000000           0.03 ns/op
ok      command-line-arguments  1.468s

あとはheapを使った実装も試してみた。先頭１００コだけ、とかならheap使ったほうが速いです。

BenchmarkSortByInterface    2000000000           0.06 ns/op
BenchmarkSortByBuiltin  2000000000           0.03 ns/op
BenchmarkSortByHeap 2000000000           0.02 ns/op

package my_sort_test

import (
    // "fmt"
    "container/heap"
    "math/rand"
    "reflect"
    "sort"
    "testing"
)

var M map[int]int

func initialize() {
    M = make(map[int]int)
    for i := 0; i < 100000; i++ {
        M[rand.Int()] = i
    }
}

// reflectを使った場合
func BenchmarkSortByInterface(b *testing.B) {
    initialize()
    keys := reflect.ValueOf(M).MapKeys()
    sort.Sort(&IntKeySorter{keys})
    for i := 0; i < len(keys); i++ {
    }
}

// 配列にコピーした場合
func BenchmarkSortByBuiltin(b *testing.B) {
    initialize()
    keys := make([]int, len(M))
    for k, _ := range M {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    for i := 0; i < len(keys); i++ {
    }
}

// heapを使った場合
func BenchmarkSortByHeap(b *testing.B) {
    initialize()
    h := NewIntHeap(len(M))
    for k, _ := range M {
        heap.Push(h, k)
    }
    for h.Len() > 0 {
        heap.Pop(h)
    }
}

type IntKeySorter struct {
    v []reflect.Value
}

func (v *IntKeySorter) Len() int {
    return len(v.v)
}

func (v *IntKeySorter) Swap(i, j int) {
    v.v[i], v.v[j] = v.v[j], v.v[i]
}

func (v *IntKeySorter) Less(i, j int) bool {
    return v.v[i].Int() < v.v[j].Int()
}

// An IntHeap is a min-heap of ints.
type IntHeap struct {
    s []int
    l int
}

func NewIntHeap(size int) *IntHeap {
    return &IntHeap{make([]int, 0, size), 0}
}

func (h *IntHeap) Len() int           { return h.l }
func (h *IntHeap) Less(i, j int) bool { return h.s[i] < h.s[j] }
func (h *IntHeap) Swap(i, j int)      { h.s[i], h.s[j] = h.s[j], h.s[i] }

func (h *IntHeap) Push(x interface{}) {
    h.s = append(h.s, x.(int))
    h.l++
}

func (h *IntHeap) Pop() interface{} {
    x := h.s[h.l-1]
    h.l--
    return x
}