-
Notifications
You must be signed in to change notification settings - Fork 14
/
ordered_map_O_test.go
69 lines (58 loc) · 1.64 KB
/
ordered_map_O_test.go
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 collections
import (
"runtime"
"sort"
"testing"
)
type tester interface {
has(int) bool
}
type mapTester struct {
m map[int]bool
}
func (m *mapTester) has(x int) bool {
_, ok := m.m[x]
return ok
}
type sliceTester struct {
s []int
}
func (s *sliceTester) has(x int) bool {
// sort.Search 使用的是二分查找
i := sort.Search(len(s.s), func(i int) bool { return s.s[i] >= x })
// 未找到时 i 为 -1
return i < len(s.s) && s.s[i] == x
}
func genMap(size int) tester {
m := map[int]bool{}
for i := 0; i < size; i++ {
m[i] = true
}
return &mapTester{m: m}
}
func genSlice(size int) tester {
s := make([]int, size)
for i := 0; i < size; i++ {
s[i] = i
}
return &sliceTester{s: s}
}
func benchmark(r tester, b *testing.B) {
runtime.GC()
b.ResetTimer()
for i := 0; i < b.N; i++ {
r.has(i)
}
}
func BenchmarkMap10e1(b *testing.B) { benchmark(genMap(10e1), b) }
func BenchmarkSlice10e1(b *testing.B) { benchmark(genSlice(10e1), b) }
func BenchmarkMap10e2(b *testing.B) { benchmark(genMap(10e2), b) }
func BenchmarkSlice10e2(b *testing.B) { benchmark(genSlice(10e2), b) }
func BenchmarkMap10e3(b *testing.B) { benchmark(genMap(10e3), b) }
func BenchmarkSlice10e3(b *testing.B) { benchmark(genSlice(10e3), b) }
func BenchmarkMap10e4(b *testing.B) { benchmark(genMap(10e4), b) }
func BenchmarkSlice10e4(b *testing.B) { benchmark(genSlice(10e4), b) }
func BenchmarkMap10e5(b *testing.B) { benchmark(genMap(10e5), b) }
func BenchmarkSlice10e5(b *testing.B) { benchmark(genSlice(10e5), b) }
func BenchmarkMap10e6(b *testing.B) { benchmark(genMap(10e6), b) }
func BenchmarkSlice10e6(b *testing.B) { benchmark(genSlice(10e6), b) }