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