前面已经分析过在少量键值对检索的场景下，map的性能不如字符串数组直接检索。当时我们是用字符串数组循环遍历的方式做的测试。而实际上这种方式还有优化的空间。下面我们就来分析下字符串数组如何检索。
字符串==
看下面字符串比较的性能基准测试：
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
|
func CompareString(str1 string, str2 string) int {
if str1 == str2 {
return 5
}
return 7
}
func CompareChar(str1 string, str2 string) int {
if str1[0] == str2[0] {
return 5
}
return 7
}
// 字符串比较，是先比较指针地址和字符长度
var str1 = "user_name_user_age_created_at"
var str2 = "user_name_user_age_created_at_1"
var str3 = "user_name_user_age_created_at_2"
func BenchmarkCompareString1(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
CompareString(str1, str2)
}
}
func BenchmarkCompareString2(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
CompareString(str2, str3)
}
}
func BenchmarkCompareString3(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
CompareChar(str2, str3)
}
}
|
性能结果如下
cpu: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
BenchmarkCompareString1-8 1000000000 0.5528 ns/op 0 B/op 0 allocs/op
BenchmarkCompareString2-8 227597743 5.273 ns/op 0 B/op 0 allocs/op
BenchmarkCompareString3-8 1000000000 0.3811 ns/op 0 B/op 0 allocs/op
大家可以改变传入字符串的值，在不同情况下比较性能，肯定会有些微妙的变化。
结论：
字符串==比较，先判断地址和长度是否一致，根本不可能相等就直接返回false，否则循环比较每个字符。
比较少数几个字符就能判断字符串不可能相等时，性能远比两字符串直接==判断要好。
字符串数组排序检索
标准库中一些实用的字符串数组处理函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
keys = []string{"name", "age", "created_at", "updated_at", "open_time"}
// 按字符串字符值，从小到达排序
sort.Strings(keys)
// 用二分查找法从字符串数组中检索item
func SearchSort(item string) int {
return sort.SearchStrings(keys, item)
}
// 自定义排序规则，比如这里按字符串长度从小到大排序keys
sort.Slice(keys, func(i, j int) bool {
return len(keys[i]) < len(keys[j])
})
|
在字符串数组长度特别大的时候，比如万级以上，用sort.SearchStrings函数，对已排好序的数组二分查找会非常快。
少量字符串的快速检索
这里介绍一种快速检索字符串数组的方法；这是我在想尽办法优化GoFast框架过程中想到的办法，有一定适用场景。
先说好前提条件，字符串不能特别多。比如Web表单提交键值对，struct变量绑定值等场景。其实这一类场景还挺多的，而通常我们都用map处理。
直接上方法，并测试性能：
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
var fls []string
var arrValuePool sync.Pool
func InitData(fields []string) {
// 字符串数组必须是按照字符串长度从小到大排好序的
fls = fields
arrValuePool.New = func() any {
arr := make([]string, len(fls))
return &arr
}
}
// 用map来存取
func SearchFromHash() int {
pms := make(map[string]string, 8)
for i := range fls {
pms[fls[i]] = fls[i]
}
total := 0
for k := range pms {
total += int(pms[k][0])
}
return total
}
// 用字符串数组存取，不过检索是循环遍历直接==比较法
func SearchFromArray() int {
pms := arrValuePool.Get().(*[]string)
for i := range *pms {
(*pms)[i] = ""
}
for i := range fls {
for j := range fls {
if fls[i] == fls[j] {
(*pms)[i] = fls[i]
break
}
}
}
total := 0
for i := range fls {
for j := range fls {
if fls[i] == fls[j] {
total += int((*pms)[i][0])
break
}
}
}
arrValuePool.Put(pms)
return total
}
// 用字符串数组存取，通过改进后的检索方法检索
func SearchFromArrayPow() int {
pms := arrValuePool.Get().(*[]string)
for i := range *pms {
(*pms)[i] = ""
}
for i := range fls {
idx := searchString(fls[i])
if idx >= 0 {
(*pms)[idx] = fls[i]
break
}
}
total := 0
for i := range fls {
idx := searchString(fls[i])
if idx >= 0 {
total += int((*pms)[idx][0])
break
}
}
arrValuePool.Put(pms)
return total
}
// 从已经按照字符串长度从小到大顺序排号的数组中，快速检索
func searchString(str string) int {
for i := range fls {
if len(fls[i]) < len(str) {
continue
}
if len(fls[i]) > len(str) {
break
}
if fls[i][0] == str[0] {
if fls[i][len(fls[i])-1] == str[len(str)-1] {
if fls[i] == str {
return i
}
}
}
}
return -1
}
// 基准测试
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
var keys []string
func init() {
runtime.GOMAXPROCS(8)
keys = []string{"user_name", "user_age", "created_at", "updated_at", "open_time",
"address", "toys", "status"}
sort.Slice(keys, func(i, j int) bool {
return len(keys[i]) < len(keys[j])
})
InitData(keys)
}
func BenchmarkHashString(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
SearchFromHash()
}
}
func BenchmarkArrayString(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
SearchFromArray()
}
}
func BenchmarkArrayPowString(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
SearchFromArrayPow()
}
}
|
长度为8，看结果（如果字符串不同，结果会稍有差异）：
cpu: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
BenchmarkHashString-8 5288106 226.1 ns/op 0 B/op 0 allocs/op
BenchmarkArrayString-8 9568843 124.7 ns/op 0 B/op 0 allocs/op
BenchmarkArrayPowString-8 54616952 21.92 ns/op 0 B/op 0 allocs/op
长度为24，看结果：
cpu: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
BenchmarkHashString-8 589944 1888 ns/op 1944 B/op 2 allocs/op
BenchmarkArrayString-8 1506367 799.0 ns/op 0 B/op 0 allocs/op
BenchmarkArrayPowString-8 52280292 23.52 ns/op 0 B/op 0 allocs/op
惊讶了吧，其实直接用map存取数据在很多场合都是不合适的，而很多Gopher滥用了map而不自知。
上面检索性能提高主要是基于以下几点：
- 字符串==比较是先比较长度，长度都不一样时，根本就不会逐字符比较了。
- 像Web表单提交，struct实体字段检索等场景下，长度相等时，比较首尾两个字符基本上就能定位了。
- 字符串数组根据字符串长度大小排好序，提高检索效率。
总结
只有对语言的实现细节了如指掌，才能在编码过程中注意到可能的缺陷，进而想到优化办法，提升代码质量。
（完）