Golangのmapと配列の処理速度検証

はじめに

イメージとしてはわかってるけど実際にどれくらい処理速度が違うのだろうと思い試してみました。

検証環境

goのバージョンは1.11.1です

bash.sh

[rssh@localhost test]$ go version
go version go1.11.1 linux/amd64

検証

早速ソースを見てみましょう

main.go

[rssh@localhost optimize]$ cat main.go
package main

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

type measure struct {
        s string
        t time.Time
}

func (d *measure) e() {
        fmt.Println(d.s, time.Now().Sub(d.t))
}
func m(s string) *measure {
        return &measure{s, time.Now()}
}

type data struct {
        id   int
        name string
}

func execSlice(maxNum int) {
        defer m("execSlice :").e()

        src := make([]data, 0, maxNum)
        func() {
                defer m("  create data").e()
                for i := 0; i < maxNum; i++ {
                        index := i + 1
                        src = append(src, data{index, getRandomWord(5)})
                }
        }()

        fSearch := func(src []data, id int) *data {
                for index, val := range src {
                        if val.id != id {
                                continue
                        }
                        return &src[index]
                }
                return nil
        }

        func() {
                defer m("  search data").e()

                fmt.Println("    ", *fSearch(src, 1))
                if maxNum < 2 {
                        return
                }
                fmt.Println("    ", *fSearch(src, maxNum/2))
                fmt.Println("    ", *fSearch(src, maxNum))
        }()
}
func execMap(maxNum int) {
        defer m("execMap   :").e()

        src := make(map[int]data, maxNum)
        func() {
                defer m("  create data").e()
                for i := 0; i < maxNum; i++ {
                        index := i + 1
                        src[index] = data{index, getRandomWord(5)}
                }
        }()

        func() {
                defer m("  search data").e()

                fmt.Println("    ", src[1])
                if maxNum < 2 {
                        return
                }
                fmt.Println("    ", src[maxNum/2])
                fmt.Println("    ", src[maxNum])
        }()
}
func getRandomWord(n int) string {
        const availableWord = `abcdefghijklmnopqrstuvwxyz0123456789!"#$%&'()=~^\{}*+<>?_,.;:[]@` + "`"

        var ret string
        for i := 0; i < n; i++ {
                ret += string(availableWord[rand.Intn(len(availableWord))])
        }
        return ret
}

func main() {
        const maxNum = 100

        defer fmt.Println("end")
        fmt.Println("start")

        fmt.Println("---------- slice")

        execSlice(maxNum)

        fmt.Println("---------- map")

        execMap(maxNum)
}

これを実行した結果はこのようになります。

const maxnum = 100

	全体の時間	データ作成	検索処理
slice	79.69µs	34.25µs	13.833µs
map	110.083µs	97.984µs	5.892µs

今回のソースだとmaxNumが100でした。

次にmaxNumを1万にして試してみましょう

const maxnum = 10000

	全体の時間	データ作成	検索処理
slice	3.648667ms	3.556381ms	23.338µs
map	4.802722ms	4.790609ms	5.619µs

次にmaxNumを100万にして試してみましょう

const maxnum = 1000000

	全体の時間	データ作成	検索処理
slice	387.434981ms	382.712523ms	2.676419ms
map	978.838246ms	978.800612ms	9.906µs

次にmaxNumを1000万にして試してみましょう

const maxnum = 10000000

	全体の時間	データ作成	検索処理
slice	4.071818417s	4.024312444s	28.304528ms
map	9.40276568s	9.402727732s	10.102µs

ふむふむ、わかってきました。
sliceはデータが増えると線形に処理時間がかかります。
mapはデータが増えるとデータ作成に時間がかかりますが、検索にかかる時間はさほど変化がないです。

おわりに

mapと配列の使い所を改めて考えてみると処理速度が向上したりするかもしれませんので、是非考えてみて下さい。

ちなみに今回は特に書いてませんが、メモリの使用量もmapと配列で全然違うのでチェックしてみると面白いと思います。