Goでmapをキー順にソートする

mapは順序を持たない

Goでmapの値は順序を持ちません。
実際下記のようなプログラムを実行してみると、実行するたびに出力順序が変わることがわかります。

package main

func main() {
	m := map[int]string{3: "c", 5: "e", 2: "b", 1: "a", 4: "d"}
	for _, e := range m {
		println(e) // この順番は実行するたびに変わる
	}
}

Go Playgroundでコードの実行ができます。
https://go.dev/play/p/jqXOpZiGafd

順序を保証するには

mapが保持しているデータの順序を保証するには、配列かスライスに入れ直してソートするしかありません。
ただ、何も考えずにループで回しながら入れ直してソートすると効率が悪くなるので、そこはシンプルに行きたいところですね。
所要時間計測のために、1000万個のデータを格納しているmapを用意し、その値をソートしてみました。
そして、所要時間比較のためにイマイチの実装とよりスマートな実行の両方を試してみました。

イマイチな実装

脳死状態で、mapの中身をsliceに入れ直してソートする方法です。
実行時間を計測してみると、あくまで一例ですが「8525 milli seconds」かかりました。
何回か実行してみても、だいたい8000ミリ秒以上かかってしまいます。
https://go.dev/play/p/ZhFI_l7Kw4t

package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
	"time"
)

func main() {
	m := getMap()

	now := time.Now()

	// 一旦sliceに入れ直す
	s := []string{}
	for _, e := range m {
		s = append(s, e)
	}

	// sliceソート
	sort.Slice(s, func(i, j int) bool {
		return strings.Compare(s[i], s[j]) > 0
	})

	fmt.Println(time.Since(now).Milliseconds(), "milli seconds")
}

func getMap() map[int]string {
	m := map[int]string{}
	for i := 0; i < 10000000; i++ {
		m[i] = strconv.Itoa(i)
	}
	return m
}

スマートな方法

上の方法に対して、mapのキーだけを格納したsliceをソートする方法です。
この方法では「4380 milli seconds」かかりました。
上の方法に比べて所要時間が半分くらいに減りましたね。
https://go.dev/play/p/PTiOsdG7bv6

package main

import (
	"fmt"
	"sort"
	"strconv"
	"time"
)

func main() {
	m := getMap()

	now := time.Now()

	// mapのキーだけを取り出てソートする
	keys := getKeys(m)
	sort.Ints(keys)

	// 後はキーの順番で入れ直す
	s := []string{}
	for key := range keys {
		s = append(s, m[key])
	}

	fmt.Println(time.Since(now).Milliseconds(), "milli seconds")
}

func getMap() map[int]string {
	m := map[int]string{}
	for i := 0; i < 10000000; i++ {
		m[i] = strconv.Itoa(i)
	}
	return m
}

func getKeys(m map[int]string) []int {
	keys := []int{}
	for k := range m {
		keys = append(keys, k)
	}
	return keys
}