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

はじめに

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

ソースコード

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.")
}

結果

$ 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 追記

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

ソースコード

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.")
}

結果

$ 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を文字列にしてみます

type Key string

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

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

$ 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使おう