golang在字符串比较中的Trick(位运算)

golang的字符串比较

在golang的strings包当中有一个函数IndexAny:IndexAny returns the index of the first instance of any Unicode code point from chars in s, or -1 if no Unicode code point from chars is present in s.,今天无意间看到了他的底层实现,觉得很是精妙这里记录分享一下。

源代码如下:

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
// IndexAny returns the index of the first instance of any Unicode code point
// from chars in s, or -1 if no Unicode code point from chars is present in s.
func IndexAny(s, chars string) int {
if chars == "" {
// Avoid scanning all of s.
return -1
}
if len(s) > 8 {
if as, isASCII := makeASCIISet(chars); isASCII {
for i := 0; i < len(s); i++ {
if as.contains(s[i]) {
return i
}
}
return -1
}
}
for i, c := range s {
for _, m := range chars {
if c == m {
return i
}
}
}
return -1
}
type asciiSet [8]uint32
// makeASCIISet creates a set of ASCII characters and reports whether all
// characters in chars are ASCII.
func makeASCIISet(chars string) (as asciiSet, ok bool) {
for i := 0; i < len(chars); i++ {
c := chars[i]
if c >= utf8.RuneSelf {
return as, false
}
as[c>>5] |= 1 << uint(c&31)
}
return as, true
}
// contains reports whether c is inside the set.
func (as *asciiSet) contains(c byte) bool {
return (as[c>>5] & (1 << uint(c&31))) != 0
}

当需要search的字符串长度大于8的时候,会创建一个asciiset来进行检索,该优化使用了一个setmap进行比特位运算来进行检索,速度会比未优化情况下快很多。下面简单就其原理介绍一下。

在makeASCIISet当中,会使用要检索的字符串进行创建,但是前提是是要检索的是ascii字符,这点介绍完原理就会理解为什么了,代码的核心是这一行as[c>>5] |= 1 << uint(c&31) 将字符右移5位作为下标,之后将其与31做和运算得出来的结果将1左移后与as数组中结果进行或运算并存进去。直接这样看会比较突兀,比较难理解,尤其是其中的左移5,与31做和,这两个数字又是哪里来的?下面我们对照ascii表进行解释。查询链接

看完表后需要有这样几个在关键点需要记住:

  1. ascii当中0~31为不可见字符没有查找需求
  2. 2的5次方等于32
  3. 2的8次方等于128

其实右移5位表示让字符的高3位来作为as的下标,c&31表示让字符的低5位保留之后将1左移表示将该位置为1,举个例子,例如字母a在ascii当中十进制对应97二进制对应了0110 0001,经过运算之后下标分别是4以及1对于as来说相当于是as下标为4的元素对应的数字第一位为1,在indexany的函数实现中使用这种方式能够在几乎O(1)的时间内检索某个字符是否存在。当然了,这里面的5,31是根绝实际情况算出来的,

相当于使用了hash的方法进行了字符串的比较查找很是精妙:)

hello http://just4fun.im/2018/04/08/golang在字符串比较中的Trick/ bye