[TOC]
var arrInt = [10]int{1,2,3,4,5,6,7,8,9,0}
var mapInt = map[int]int{
1:1, 2:2, 3:3, 4:4, 5:5,
6:6, 7:7, 8:8, 9:9, 0:0,
}
func EachArray() {
for _, v := range arrInt {
_ = v
}
}
func EachMap() {
for _, v := range mapInt {
_ = v
}
}
// go test -v -bench . -benchmem
//BenchmarkEachArray-4 300000000 4.91 ns/op 0 B/op 0 allocs/op
//BenchmarkEachMap-4 10000000 30 ns/op 0 B/op 0 allocs/op
假设数组谁无序的,需要遍历数组
const cap = 10000
func BenchmarkArraySearch(b *testing.B) {
a := [cap]int{}
for i := 0; i < cap; i++ {
a[i] = i
}
t := cap
b.StartTimer()
for i := 0; i < b.N; i++ {
for _, v := range a {
if t == v {
break
}
}
}
b.StartTimer()
}
func BenchmarkMapSearch(b *testing.B) {
a := make(map[int]int, cap)
for i := 0; i < cap; i++ {
a[i] = i
}
t := cap
b.StartTimer()
for i := 0; i < b.N; i++ {
if v, ok := a[t]; ok {
_ = v
}
}
b.StartTimer()
}
//以此调整cap的值
//cap = 10
//BenchmarkArraySearch-4 200000000 8.73 ns/op 0 B/op 0 allocs/op
//BenchmarkMapSearch-4 100000000 1.7 ns/op 0 B/op 0 allocs/op
//cap = 100
//BenchmarkArraySearch-4 20000000 79.4 ns/op 0 B/op 0 allocs/op
//BenchmarkMapSearch-4 100000000 11.9 ns/op 0 B/op 0 allocs/op
//cap = 1000
//BenchmarkArraySearch-4 3000000 464 ns/op 0 B/op 0 allocs/op
//BenchmarkMapSearch-4 100000000 12.3 ns/op 0 B/op 0 allocs/op
//cap = 10000
//BenchmarkArraySearch-4 300000 4859 ns/op 0 B/op 0 allocs/op
//BenchmarkMapSearch-4 100000000 11.9 ns/op 0 B/op 0 allocs/op
显然,只有数据很少时,数组才能比map快,这是时间复杂度O(n)与O(1)的差距,随着数据量的增大,差距回来越大,如果是有序数组,可以通过二分查找,时间复杂度从O(n)变为O(logn), map迪称基于hash实现。如果没有rehash和过多的hash冲突,查找极快。
func SetInt8() {
var i int8
a := [30]int8{}
for i = 0; i < 30; i++ {
a[i] = i
}
}
func SetInt16() {
var i int16
a := [30]int16{}
for i = 0; i < 30; i++ {
a[i] = i
}
}
func SetInt32() {
var i int32
a := [30]int32{}
for i = 0; i < 30; i++ {
a[i] = i
}
}
func SetInt64() {
var i int64
a := [30]int64{}
for i = 0; i < 30; i++ {
a[i] = i
}
}
//goos: darwin
//goarch: amd64
//BenchmarkSetInt8-4 50000000 29.5 ns/op 0 B/op 0 allocs/op
//BenchmarkSetInt16-4 100000000 18.8 ns/op 0 B/op 0 allocs/op
//BenchmarkSetInt32-4 50000000 28.9 ns/op 0 B/op 0 allocs/op
//BenchmarkSetInt64-4 100000000 11.9 ns/op 0 B/op 0 allocs/op
这里不同的数组设置,int8最慢,int64反而上最快的。这是为什么呢?