2️⃣
Goの2次元mapをgenericsで扱いやすくする
TL;DR
前書き
趣味で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) | 52971(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) | 52971(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良い
Discussion