Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

はじめに

  • これまでPythonをメインで書いてきて、ループは悪だと思っていた
  • GoとかCとか回しても早い言語を使い始めて、考え方が変わってきた
  • key:valueのセットを保持する際、mapで保持する方法と、arrayで保持する方法を比較してみた
    • 方法1:map[key]valueで保持してmap[key]で取り出す
    • 方法2:[]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使おう
ryskiwt
IoTプラットフォームを手がけるベンチャー企業でVPoPをやっています。 Golang/Java/Python/JavaScript、統計学/時系列解析/信号処理/移動体通信工学
aptpod
"日本のIoT、M2Mを牽引するテクノロジーカンパニーです。⾃動⾞やロボット・産業機械などから短周期に発生する制御・センサーデータをモバイル・インターネット網を介し、⾼速・大容量且つ安定的に、そして双方向に伝送し、回収データの可視化・解析や遠隔制御を実現するプロダクト開発を行っています。"
https://www.aptpod.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away