map vs array (Golangベンチマークテストの練習を兼ねて)

はじめに
--------------------

- これまでPythonをメインで書いてきて、ループは悪だと思っていた
- GoとかCとか回しても早い言語を使い始めて、考え方が変わってきた
- key:valueのセットを保持する際、mapで保持する方法と、arrayで保持する方法を比較してみた
    - 方法１：`map[key]value`で保持して`map[key]`で取り出す
    - 方法２：`[]value`で保持して、ループ回して探して取り出す

ソースコード
--------------------

```go:main.go
package main

import (
	"fmt"
	"math/rand"
	"time"
)

type KeyValue struct {
	Key   int
	Value string
}

func main() {
	NUM := 100000000
	nums := []int{10, 20, 50, 100, 1000}

	for _, num := range nums {
		r := make([]int, NUM)
		rand.Seed(time.Now().UnixNano())
		for i := 0; i < NUM; i++ {
			r[i] = rand.Intn(num)
		}

		m := make(map[int]KeyValue)
		a := make([]KeyValue, num)

		for i := 0; i < num; i++ {
			m[i] = KeyValue{
				Key:   i,
				Value: "",
			}

			a[i] = KeyValue{
				Key:   i,
				Value: "",
			}
		}

		tic := time.Now()
		for i := 0; i < NUM; i++ {
			findFromMap(r[i], m)
		}
		toc1 := time.Now()

		for i := 0; i < NUM; i++ {
			findFromArray(r[i], a)
		}
		toc2 := time.Now()

		timeMap := float64((toc1.Sub(tic)).Nanoseconds()) / float64(NUM)
		timeAry := float64((toc2.Sub(toc1)).Nanoseconds()) / float64(NUM)
		fmt.Printf("要素数 %5d : map=%10.5f[nsec], ary=%10.5f[nsec]\n", num, timeMap, timeAry)
	}
}

func findFromMap(key int, m map[int]KeyValue) (KeyValue, error) {
	if kv, ok := m[key]; !ok {
		return KeyValue{}, fmt.Errorf("not exists.")

	} else {
		return kv, nil
	}
}

func findFromArray(key int, a []KeyValue) (KeyValue, error) {
	for _, kv := range a {
		if kv.Key == key {
			return kv, nil
		}
	}

	return KeyValue{}, fmt.Errorf("not exists.")
}
```

結果
--------------------
```shell-session
$ go run main.go
要素数    10 : map=  34.53508[nsec], ary=  18.53113[nsec]
要素数    20 : map=  34.75044[nsec], ary=  19.78009[nsec]
要素数    50 : map=  37.55749[nsec], ary=  35.05825[nsec]
要素数   100 : map=  35.14514[nsec], ary=  43.78907[nsec]
要素数  1000 : map=  36.16042[nsec], ary= 336.10308[nsec]
$ go run main.go
要素数    10 : map=  31.30338[nsec], ary=  15.72180[nsec]
要素数    20 : map=  35.51624[nsec], ary=  20.84568[nsec]
要素数    50 : map=  33.89756[nsec], ary=  28.58386[nsec]
要素数   100 : map=  35.77122[nsec], ary=  46.12543[nsec]
要素数  1000 : map=  35.11392[nsec], ary= 342.29167[nsec]
```

- mapは要素数が増えても安定して同じ位の時間
- aryは早期リターンできるからか、要素数50個くらいまではmapより速い

感想
--------------------

- 普段よく使うくらいの要素数（0~20程度）だとarryのほうが速いかもっていうのが驚き
- mapの方、要素数増えても時間変わんないのすごい

2017/04/15 追記
====================

- ベンチマークテストの形式に書き直して見ました

ソースコード
--------------------

```go:main_test.go
package main

import (
	"fmt"
	"math/rand"
	"testing"
	"time"
)

var (
	SIZES = []int{10, 20, 50, 100, 1000}
)

type Key int

func int2key(i int) Key {
	return Key(i)
}

type KeyValue struct {
	Key   Key
	Value string
}

func BenchmarkMapVsArry(b *testing.B) {
	for _, size := range SIZES {
		m, a := setUp(size)

		b.Run(fmt.Sprintf("Map(size=%d)", size), createBenchmarkMapFunc(size, m))
		b.Run(fmt.Sprintf("Ary(size=%d)", size), createBenchmarkAryFunc(size, a))
	}
}

func setUp(size int) (m map[Key]KeyValue, a []KeyValue) {
	m = make(map[Key]KeyValue)
	a = make([]KeyValue, size)

	for i := 0; i < size; i++ {
		m[int2key(i)] = KeyValue{
			Key:   int2key(i),
			Value: "",
		}

		a[i] = KeyValue{
			Key:   int2key(i),
			Value: "",
		}
	}

	return m, a
}

func createRandomKeys(iterNum, size int) (r []Key) {
	rand.Seed(time.Now().UnixNano())

	r = make([]Key, iterNum)
	for i := 0; i < iterNum; i++ {
		r[i] = int2key(rand.Intn(size))
	}

	return r
}

func createBenchmarkMapFunc(size int, m map[Key]KeyValue) func(*testing.B) {
	return func(b *testing.B) {
		r := createRandomKeys(b.N, size)
		b.ResetTimer()

		for i := 0; i < b.N; i++ {
			findFromMap(r[i], m)
		}
	}
}

func findFromMap(key Key, m map[Key]KeyValue) (KeyValue, error) {
	if kv, ok := m[key]; !ok {
		return KeyValue{}, fmt.Errorf("not exists.")

	} else {
		return kv, nil
	}
}

func createBenchmarkAryFunc(size int, a []KeyValue) func(*testing.B) {
	return func(b *testing.B) {
		r := createRandomKeys(b.N, size)
		b.ResetTimer()

		for i := 0; i < b.N; i++ {
			findFromAry(r[i], a)
		}
	}
}

func findFromAry(key Key, a []KeyValue) (KeyValue, error) {
	for _, kv := range a {
		if kv.Key == key {
			return kv, nil
		}
	}

	return KeyValue{}, fmt.Errorf("not exists.")
}
```

結果
--------------------

```shell-session
$ go test -bench .
testing: warning: no tests to run
BenchmarkMapVsArry/Map(size=10)-4         	50000000	        28.6 ns/op
BenchmarkMapVsArry/Ary(size=10)-4         	100000000	        16.1 ns/op
BenchmarkMapVsArry/Map(size=20)-4         	50000000	        29.9 ns/op
BenchmarkMapVsArry/Ary(size=20)-4         	100000000	        20.1 ns/op
BenchmarkMapVsArry/Map(size=50)-4         	50000000	        30.9 ns/op
BenchmarkMapVsArry/Ary(size=50)-4         	50000000	        27.8 ns/op
BenchmarkMapVsArry/Map(size=100)-4        	50000000	        32.6 ns/op
BenchmarkMapVsArry/Ary(size=100)-4        	30000000	        41.4 ns/op
BenchmarkMapVsArry/Map(size=1000)-4       	50000000	        32.6 ns/op
BenchmarkMapVsArry/Ary(size=1000)-4       	 5000000	       285 ns/op
PASS
ok  	none/goexp/mapvsarry	37.021s
```

文字列の場合
--------------------
- keyを文字列にしてみます

```go
type Key string

func int2key(i int) Key {
	return Key(strconv.Itoa(i))
}
```

- Mapは10nsくらい遅くなった
- Aryの性能低下が激しい

```shell-session
$ go test -bench .
testing: warning: no tests to run
BenchmarkMapVsArry/Map(size=10)-4         	30000000	        40.5 ns/op
BenchmarkMapVsArry/Ary(size=10)-4         	30000000	        45.0 ns/op
BenchmarkMapVsArry/Map(size=20)-4         	30000000	        39.6 ns/op
BenchmarkMapVsArry/Ary(size=20)-4         	30000000	        57.9 ns/op
BenchmarkMapVsArry/Map(size=50)-4         	50000000	        40.5 ns/op
BenchmarkMapVsArry/Ary(size=50)-4         	10000000	       129 ns/op
BenchmarkMapVsArry/Map(size=100)-4        	30000000	        40.6 ns/op
BenchmarkMapVsArry/Ary(size=100)-4        	 5000000	       257 ns/op
BenchmarkMapVsArry/Map(size=1000)-4       	30000000	        42.9 ns/op
BenchmarkMapVsArry/Ary(size=1000)-4       	  500000	      2424 ns/op
PASS
ok  	none/goexp/mapvsarry	40.567s
```

結論
--------------------

- Key:Value構造のデータは、おとなしくビルトインのmap使おう