Go中的map和slice查询性能对比

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

package main

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

const maxSize = 50
const tests = 20000000
const findMult = 1 //9999999999 // 100 = 1% hit rate, 1 = 100% hit rate.

type lst []int

func (l lst) has(xxxx int) bool {
	for _, i := range l {
		if i == xxxx {
			return true
		}
	}
	return false
}

type mp map[int]struct{}

func (m mp) has(xxxx int) bool {
	_, ok := m[xxxx]
	return ok
}

func main() {
	rand.Seed(time.Now().UnixNano())

	for size := 1; size < maxSize; size++ {
		l := make(lst, 0, size)
		m := make(mp, size)
		for i := 0; i < size; i++ {
			e := rand.Int()
			l = append(l, e)
			m[e] = struct{}{}
		}

		found := 0
		start := time.Now()
		for x := 0; x < tests; x++ {
			xxxx := rand.Intn(size * findMult)
			if l.has(xxxx) {
				found++
			}
		}
		sliceDuration := time.Now().Sub(start)

		start = time.Now()
		for x := 0; x < tests; x++ {
			xxxx := rand.Intn(size * findMult)
			if m.has(xxxx) {
				found++
			}
		}
		mapDuration := time.Now().Sub(start)

		// Do something with found so it doesn't get optimized away.
		if found > 0 {
			rand.Int()
		}

		fmt.Printf("%d\t%v\n", size, sliceDuration-mapDuration)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

1	-209.706862ms
2	-286.768577ms
3	-253.643371ms
4	-184.176088ms
5	-188.898868ms
6	-194.644208ms
7	-113.719066ms
8	-501.892168ms
9	-34.573439ms
10	-380.242983ms
11	-216.931934ms
12	-631.616472ms
13	-135.392189ms
14	-229.107952ms
15	-114.9351ms
16	-373.97338ms
17	-287.007278ms
18	-34.734517ms
19	-237.892748ms
20	-222.025115ms
21	-140.869821ms
22	13.382928ms
23	-341.238616ms
24	-281.6694ms
25	70.841324ms
26	63.31161ms
27	-179.818415ms
28	-30.357644ms
29	39.261291ms
30	-50.066403ms
31	-75.68084ms
32	113.281835ms
33	119.597633ms
34	222.476972ms
35	-89.222024ms
36	95.265413ms
37	164.569075ms
38	150.392782ms
39	247.403261ms
40	365.580116ms
41	284.544515ms
42	275.936162ms
43	330.8626ms
44	428.790859ms
45	94.745088ms
46	388.334553ms
47	189.708983ms
48	387.604493ms
49	308.960719ms