search
LoginSignup
1
Help us understand the problem. What are the problem?

posted at

updated at

Goの2次元mapをgenericsで扱いやすくする

TL;DR

Githubのコード読んでみてください.

前書き

趣味でgolangのHMM音声認識エンジンを作っている際,bigramやtrigramの確率保存で複数キーからなる連想配列が欲しくなりました.
パッと思いつくのは二次元mapかなと思いましたが,別で良い感じのライブラリか何かないかなと探していました.

記事を探していると[Goで多重連想配列]があり,確かに何も考えずに二次元のmapにアクセスするとヌルポになりそうということが分かりました.
少し処理が煩わしいのでもっと綺麗に作れないかなと思い探していると,[Goで多次元マップ(複数のキーからなるマップ)を実現したいときにはどうするか]という記事を見つけてカッコイイと思いました.

そこで実際どれが良いかなと思い実験してみることにしました.

問題

2次元map

map[string]map[string]int

keys struct map

type Keys struct {
	key1, key2 string
}
map[Keys]int

どちらが速いのか100×100,1000×1000,10000×10000のマッピングで比較してみました.
今回は2つのキーどちらもstringで実験を行なっています.

Map生成

100×100 1000×1000 10000×10000
2次元map 0.86(ms) 111(ms) 13086(ms)
mapKeys 1.31(ms) 241(ms) 52972(ms)

Mapアクセス(すべてのKeyにアクセス)

100×100 1000×1000 10000×10000
2次元map 0.43(ms) 45(ms) 6018(ms)
mapKeys 0.39(ms) 114(ms) 24382(ms)

結果を見るとキーや要素数が少ない場合はstructをキーにして問題なさそうですが,数が増えると速度の差が顕著になってきますね.
今回キーの組み合わせが数万とあるので個人的に「良い感じ」と思った構造体をKeyにする場合は処理が遅くなってしまいそうです.

解決法

go1.18でgenericsが導入されたので,2次元mapをwrapした良い感じのtypeを作ることにしました.
以下のようにMap2Dimと定義して必要そうなメソッドを生やしました.
これでヌルポも防げて綺麗に書けそうです.

type Map2Dim[K1, K2 comparable, V any] map[K1]map[K2]V

func (m Map2Dim[K1, K2, V]) Set(key1 K1, key2 K2, val V) {
	if m[key1] == nil {
		m[key1] = make(map[K2]V)
		m[key1][key2] = val
	} else {
		m[key1][key2] = val
	}
}

func (m Map2Dim[K1, K2, V]) Get(key1 K1, key2 K2) V {
	if m[key1] == nil {
		m[key1] = make(map[K2]V)
	}
	return m[key1][key2]
}

func (m Map2Dim[K1, K2, V]) Gets(key1 K1, key2 K2) (val V, ok bool) {
	if m[key1] == nil {
		m[key1] = make(map[K2]V)
	}
	val, ok = m[key1][key2]
	return
}

func (m Map2Dim[K1, K2, V]) HasKey(key1 K1, key2 K2) bool {
	if m[key1] == nil {
		return false
	}
	_, ok := m[key1][key2]
	return ok
}

速度比較

速度も重視していたので比較してみます.

Map生成

100×100 1000×1000 10000×10000
2次元map 0.86(ms) 111(ms) 13086(ms)
mapKeys 1.31(ms) 241(ms) 52972(ms)
Map2Dim 0.96(ms) 121(ms) 17692(ms)

Mapアクセス(すべてのKeyにアクセス)

100×100 1000×1000 10000×10000
2次元map 0.43(ms) 45(ms) 6018(ms)
mapKeys 0.39(ms) 114(ms) 24382(ms)
Map2Dim 0.53(ms) 54(ms) 6451(ms)

結果からすると許容範囲くらいの差で使えそうです.

使用例

githubに載せているのでご覧ください.

終わりに

generics良いぃ

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
1
Help us understand the problem. What are the problem?