golang在字符串比较中的Trick（位运算）

Posted on | In , | | 浏览 次

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的方法进行了字符串的比较查找很是精妙：）

转载请注明来源链接 http://just4fun.im/2018/04/08/golang在字符串比较中的Trick/ 尊重知识,谢谢:)