こんにちは。サーバサイドエンジニアの藤原です。
コーヒーはローソン派です。
今までは店員さんが淹れてくれてましたが、最近自分で淹れる方式に変わっちゃいましたね。
うちの近くのローソンだけなのかな🤔
味も微妙に変わってるんですよね。
ということで、HRBrain Advent Calendar 6日目を担当させていただきます。 qiita.com
map or slice どっちかね？
go言語で検索や突き合わせ処理をパフォーマンスを考慮して実装する際に、sliceを使うべきかｍapを使うべきか迷われたことはないでしょうか。
自分は、なんとなくKeyのバリエーションが多い場合はmapにしたほうが計算量が一定だから良さそうだよなーと思い、mapを使うケースが多いです。
しかし、果たしてそれで合っているのか前から気になってました。そこで今回改めてちゃんと調べてみました。
ポイント💡
単純に検索スピードだけ考えるとmapのほうが有利なのですが、実際にmapを使おうと思うとsliceからmapへの変換処理が必要です。
今回はそこも加味して計測します。
また、sliceの検索は線形探索と二分探索の２パターンで試したいと思います。二分探索の場合は事前のソートが必要ですのでそこも加味します。
まとめると、試すのは以下の3パターンです。
- slice：線形探索
- slice：ソート+二分探索
- map：sliceをmap変換 + map検索
また、検索対象のデータの件数に加え、検索の実施回数もポイントになると思いますのでその組み合わせもいくつか試してみたいと思います。
実装
検索対象のデータ(intのslice)と検索データ(intのslice)を渡して、検索データが見つかった位置の一覧を返すというプログラムを書きます。 検索データが見つからない場合は-1を詰めます。
線形探索
// LinearSearch 線形探索 func LinearSearch(nums, searches []int) (pos []int) { pos = make([]int, len(searches)) for si, s := range searches { pos[si] = -1 for i, num := range nums { if s == num { pos[si] = i break } } } return pos }
ソート+二分探索
// BinarySearch 二分探索 func BinarySearch(nums, searches []int) (pos []int) { sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] }) return binarySearch(nums, searches) } // numsはソート済み func binarySearch(nums, searches []int) (pos []int) { pos = make([]int, len(searches)) for si, s := range searches { idx := sort.Search(len(nums), func(i int) bool { return nums[i] >= s }) if idx < len(nums) && nums[idx] == s { pos[si] = idx } else { pos[si] = -1 } } return pos }
sliceをmap変換 + map検索
// MapSearch ハッシュ(Map)探索 func MapSearch(nums, searches []int) (pos []int) { m := sliceToMap(nums) return mapSearch(m, searches) } func mapSearch(m map[int]int, searches []int) (pos []int) { pos = make([]int, len(searches)) for si, s := range searches { if idx, ok := m[s]; ok { pos[si] = idx } else { pos[si] = -1 } } return pos } func sliceToMap(nums []int) map[int]int { m := make(map[int]int, len(nums)) for i, num := range nums { m[num] = i } return m }
データ
検索対象のデータと検索データの組み合わせは以下を用意します。
| 検索対象のデータ件数 | 検索データ件数 |
|---|---|
| 1000 | 3 |
| 1000 | 100 |
| 1000 | 1000 |
| 10000 | 3 |
| 10000 | 100 |
| 10000 | 1000 |
| 10000 | 10000 |
| 50000 | 10000 |
また、線形探索はデータの一致する位置次第で計算量に差が出てしまうので、 今回は「先頭から順に一致するパターン」と「全く一致しないパターン」の２パターンにします。 「全く一致しないパターン」の場合、検索対象のデータを全て見るという動きになるので線形探索にとっては不利にはなります。
計測用の実装
goのbenchmark機能を用いて計測します。
冗長なテストコードは見るのも直すのも辛いのでこんな感じで共通化します。
type searchFunc func(nums, searches []int) (pos []int) func commonBenchmark(b *testing.B, nums, searches []int, f searchFunc) { b.ResetTimer() for i := 0; i < b.N; i++ { f(nums, searches) } }
そしてこのように引数変えるだけで、いい感じになるようにします。
// // data-1000, search-3 // func Benchmark_LinearSearch_1000__3(b *testing.B) { commonBenchmark(b, nums1000, search3, LinearSearch) } func Benchmark_BinarySearch_1000__3(b *testing.B) { commonBenchmark(b, nums1000, search3, BinarySearch) } // // data-1000, search-100 // func Benchmark_LinearSearch_1000__100(b *testing.B) { commonBenchmark(b, nums1000, search100, LinearSearch) }
結果
準備できましたので、動かしてみましょう！
go test -bench . -benchmem Benchmark_LinearSearch_1000__3_NotFound-12 1200898 1041 ns/op 32 B/op 1 allocs/op Benchmark_BinarySearch_1000__3_NotFound-12 35037 34245 ns/op 96 B/op 3 allocs/op Benchmark_binarySearch_1000__3_NotFound-12 9712423 115 ns/op 32 B/op 1 allocs/op Benchmark_MapSearch____1000__3_NotFound-12 38277 32859 ns/op 41193 B/op 8 allocs/op Benchmark_mapSearch____1000__3_NotFound-12 17367688 61.9 ns/op 32 B/op 1 allocs/op Benchmark_LinearSearch_1000__100_NotFound-12 41889 29805 ns/op 896 B/op 1 allocs/op Benchmark_BinarySearch_1000__100_NotFound-12 30975 37237 ns/op 960 B/op 3 allocs/op Benchmark_binarySearch_1000__100_NotFound-12 342697 3282 ns/op 896 B/op 1 allocs/op Benchmark_MapSearch____1000__100_NotFound-12 36074 32351 ns/op 42057 B/op 8 allocs/op Benchmark_mapSearch____1000__100_NotFound-12 783559 1288 ns/op 896 B/op 1 allocs/op Benchmark_LinearSearch_1000__1000_NotFound-12 3541 287076 ns/op 8192 B/op 1 allocs/op Benchmark_BinarySearch_1000__1000_NotFound-12 18427 67671 ns/op 8256 B/op 3 allocs/op Benchmark_binarySearch_1000__1000_NotFound-12 37875 31188 ns/op 8192 B/op 1 allocs/op Benchmark_MapSearch____1000__1000_NotFound-12 27123 45042 ns/op 49353 B/op 8 allocs/op Benchmark_mapSearch____1000__1000_NotFound-12 83547 12659 ns/op 8192 B/op 1 allocs/op Benchmark_LinearSearch_10000_3_NotFound-12 133090 10778 ns/op 32 B/op 1 allocs/op Benchmark_BinarySearch_10000_3_NotFound-12 1992 587961 ns/op 96 B/op 3 allocs/op Benchmark_binarySearch_10000_3_NotFound-12 6005101 195 ns/op 32 B/op 1 allocs/op Benchmark_MapSearch____10000_3_NotFound-12 3416 370013 ns/op 322289 B/op 13 allocs/op Benchmark_mapSearch____10000_3_NotFound-12 19178061 63.1 ns/op 32 B/op 1 allocs/op Benchmark_LinearSearch_10000_100_NotFound-12 4141 272541 ns/op 896 B/op 1 allocs/op Benchmark_BinarySearch_10000_100_NotFound-12 2673 452406 ns/op 960 B/op 3 allocs/op Benchmark_binarySearch_10000_100_NotFound-12 284740 4563 ns/op 896 B/op 1 allocs/op Benchmark_MapSearch____10000_100_NotFound-12 2964 346300 ns/op 323174 B/op 13 allocs/op Benchmark_mapSearch____10000_100_NotFound-12 938948 1285 ns/op 896 B/op 1 allocs/op Benchmark_LinearSearch_10000_1000_NotFound-12 435 2870078 ns/op 8192 B/op 1 allocs/op Benchmark_BinarySearch_10000_1000_NotFound-12 2119 486083 ns/op 8256 B/op 3 allocs/op Benchmark_binarySearch_10000_1000_NotFound-12 26682 40681 ns/op 8192 B/op 1 allocs/op Benchmark_MapSearch____10000_1000_NotFound-12 3466 358536 ns/op 330494 B/op 13 allocs/op Benchmark_mapSearch____10000_1000_NotFound-12 90537 12546 ns/op 8192 B/op 1 allocs/op Benchmark_LinearSearch_10000_10000_NotFound-12 38 27388279 ns/op 81920 B/op 1 allocs/op Benchmark_BinarySearch_10000_10000_NotFound-12 1333 844088 ns/op 81984 B/op 3 allocs/op Benchmark_binarySearch_10000_10000_NotFound-12 2542 417791 ns/op 81920 B/op 1 allocs/op Benchmark_MapSearch____10000_10000_NotFound-12 2362 537530 ns/op 404225 B/op 13 allocs/op Benchmark_mapSearch____10000_10000_NotFound-12 9194 120524 ns/op 81920 B/op 1 allocs/op Benchmark_LinearSearch_50000_10000_NotFound-12 7 171894166 ns/op 81920 B/op 1 allocs/op Benchmark_BinarySearch_50000_10000_NotFound-12 382 3537735 ns/op 81984 B/op 3 allocs/op Benchmark_binarySearch_50000_10000_NotFound-12 2385 471677 ns/op 81920 B/op 1 allocs/op Benchmark_MapSearch____50000_10000_NotFound-12 452 2471348 ns/op 1494987 B/op 847 allocs/op Benchmark_mapSearch____50000_10000_NotFound-12 9882 178866 ns/op 81920 B/op 1 allocs/op Benchmark_LinearSearch_1000__3-12 1355110 887 ns/op 32 B/op 1 allocs/op Benchmark_BinarySearch_1000__3-12 33398 33985 ns/op 96 B/op 3 allocs/op Benchmark_binarySearch_1000__3-12 9556736 138 ns/op 32 B/op 1 allocs/op Benchmark_MapSearch____1000__3-12 33405 31856 ns/op 41193 B/op 8 allocs/op Benchmark_mapSearch____1000__3-12 21335660 50.7 ns/op 32 B/op 1 allocs/op Benchmark_LinearSearch_1000__100-12 501254 2388 ns/op 896 B/op 1 allocs/op Benchmark_BinarySearch_1000__100-12 30468 41578 ns/op 960 B/op 3 allocs/op Benchmark_binarySearch_1000__100-12 269874 3892 ns/op 896 B/op 1 allocs/op Benchmark_MapSearch____1000__100-12 35611 32581 ns/op 42057 B/op 8 allocs/op Benchmark_mapSearch____1000__100-12 1000000 1081 ns/op 896 B/op 1 allocs/op Benchmark_LinearSearch_1000__1000-12 8306 152265 ns/op 8192 B/op 1 allocs/op Benchmark_BinarySearch_1000__1000-12 10000 105576 ns/op 8256 B/op 3 allocs/op Benchmark_binarySearch_1000__1000-12 17820 68080 ns/op 8192 B/op 1 allocs/op Benchmark_MapSearch____1000__1000-12 21610 53298 ns/op 49353 B/op 8 allocs/op Benchmark_mapSearch____1000__1000-12 58798 18423 ns/op 8192 B/op 1 allocs/op Benchmark_LinearSearch_10000_3-12 1377502 874 ns/op 32 B/op 1 allocs/op Benchmark_BinarySearch_10000_3-12 2472 447825 ns/op 96 B/op 3 allocs/op Benchmark_binarySearch_10000_3-12 7272561 164 ns/op 32 B/op 1 allocs/op Benchmark_MapSearch____10000_3-12 3445 337668 ns/op 322346 B/op 13 allocs/op Benchmark_mapSearch____10000_3-12 23896603 51.3 ns/op 32 B/op 1 allocs/op Benchmark_LinearSearch_10000_100-12 504427 2480 ns/op 896 B/op 1 allocs/op Benchmark_BinarySearch_10000_100-12 2534 454719 ns/op 960 B/op 3 allocs/op Benchmark_binarySearch_10000_100-12 210144 5019 ns/op 896 B/op 1 allocs/op Benchmark_MapSearch____10000_100-12 3038 337526 ns/op 323174 B/op 13 allocs/op Benchmark_mapSearch____10000_100-12 971736 1129 ns/op 896 B/op 1 allocs/op Benchmark_LinearSearch_10000_1000-12 7874 143806 ns/op 8192 B/op 1 allocs/op Benchmark_BinarySearch_10000_1000-12 2115 530711 ns/op 8256 B/op 3 allocs/op Benchmark_binarySearch_10000_1000-12 16612 71856 ns/op 8192 B/op 1 allocs/op Benchmark_MapSearch____10000_1000-12 2916 381503 ns/op 330458 B/op 13 allocs/op Benchmark_mapSearch____10000_1000-12 81838 14044 ns/op 8192 B/op 1 allocs/op Benchmark_LinearSearch_10000_10000-12 86 13614430 ns/op 81920 B/op 1 allocs/op Benchmark_BinarySearch_10000_10000-12 945 1193840 ns/op 81984 B/op 3 allocs/op Benchmark_binarySearch_10000_10000-12 1503 790767 ns/op 81920 B/op 1 allocs/op Benchmark_MapSearch____10000_10000-12 1629 672223 ns/op 404231 B/op 13 allocs/op Benchmark_mapSearch____10000_10000-12 3331 309937 ns/op 81920 B/op 1 allocs/op Benchmark_LinearSearch_50000_10000-12 62 17120934 ns/op 81920 B/op 1 allocs/op Benchmark_BinarySearch_50000_10000-12 337 3661868 ns/op 81984 B/op 3 allocs/op Benchmark_binarySearch_50000_10000-12 1270 1031030 ns/op 81920 B/op 1 allocs/op Benchmark_MapSearch____50000_10000-12 374 2872006 ns/op 1495159 B/op 848 allocs/op Benchmark_mapSearch____50000_10000-12 4281 263885 ns/op 81920 B/op 1 allocs/op PASS ok github.com/fujiwaram/slice-vs-map 122.127s
結果（表）
分かりにくいので表形式にしてまとめました。
赤字の部分が結果が優れているものです。
列の数字は、検索対象のデータ件数と検索データ件数を示しています。
例えば、「1000-3」は「1000件の検索対象のデータから3件を検索する」パターンです。
緑の行の「Binary」はソート処理を省いたもの、「Map」はスライスからMapへの変換処理を省いたものです。参考までに計測してます。
考察
検索データ件数が100件のときは線形探索のほうが速いですが、1000件くらいからmapの検索のほうが速くなってます。
線形探索の方はデータが増えると比例して時間もかかる様になるみたいなので、だいたいこの辺りが閾値ということなのでしょう。
速度の面で見るとmapのほうが良さそうではありますが、メモリの方を見るとmapはデータ量が増えると比例してメモリの消費が増えています。 パフォーマンスを考える上でメモリの消費も気にする必要はありますので、ここはバランスを見て扱う必要がありそうです。
二分探索の方はスピード面では一位にはなれていないですが、メモリの消費量がほとんどないのにも関わらず、ある程度のスピードが出ています。
バランス考えて、二分探索を選択するというのもアリのような気がしてきました。
今回の調査の一番の収穫🌾
今回使用したコードはGitHubに上げています。
まとめ
ということで、「sliceとmapどっちが速いのだね？」の問いに対する答えとしては、
「データ量を考慮しつつ、最適なものを使いしょう」という月並みな結論になりそうです。
HRBrainではこのようなことを一緒に考えてくれる仲間を募集しています。
「そんなの知ってたぜ」というそこのあなた、ぜひご応募ください！
