内容简介:func Contains(s, substr string) boolContains()返回一个布尔值,若substr存在于s中,则返回true,不存在则返回false。我们再来看Index(),
golang源码探究-strings
Contain()
func Contains(s, substr string) bool
Contains()返回一个布尔值,若substr存在于s中,则返回true,不存在则返回false。
// Contains reports whether substr is within s func Contains(s, substr string) bool { return Index(s, substr) >= 0 }
Index()
我们再来看Index(),
func Index(s, substr string) int
Index()返回substr出现在原始string s 中的 位置,如果s中meiyousubstr,则返回-1
// Index returns the index of the first instance of substr in s, or -1 if substr is not present in s. func Index(s, substr string) int { n := len(substr) //先获取substr的长度 赋给n switch { case n == 0: //如果 substr的长度为0 ,则返回0, return 0 case n == 1: return IndexByte(s, substr[0]) // 后面再看一下IndexByte()的源码 case n == len(s): // 如果 s和substr长度相等,直接判断俩字符串是否一模一样 if substr == s { return 0 } return -1 case n > len(s): // 如果 substr的长度大于s的长度,那肯定不存在了,返回-1,说明substr不存在于s中 return -1 case n <= bytealg.MaxLen: // 后面得看bytealg.MaxLen // Use brute force when s and substr both are small if len(s) <= bytealg.MaxBruteForce { // const型 :const MaxBruteForce = 64 return bytealg.IndexString(s, substr) } c0 := substr[0] c1 := substr[1] i := 0 t := len(s) - n + 1 fails := 0 for i < t { if s[i] != c0 { // IndexByte is faster than bytealg.IndexString, so use it as long as // we're not getting lots of false positives. o := IndexByte(s[i:t], c0) if o < 0 { return -1 } i += o } if s[i+1] == c1 && s[i:i+n] == substr { return i } fails++ i++ // Switch to bytealg.IndexString when IndexByte produces too many false positives. if fails > bytealg.Cutover(i) { r := bytealg.IndexString(s[i:], substr) if r >= 0 { return r + i } return -1 } } return -1 } c0 := substr[0] c1 := substr[1] i := 0 t := len(s) - n + 1 fails := 0 for i < t { if s[i] != c0 { o := IndexByte(s[i:t], c0) if o < 0 { return -1 } i += o } if s[i+1] == c1 && s[i:i+n] == substr { return i } i++ fails++ if fails >= 4+i>>4 && i < t { // See comment in ../bytes/bytes_generic.go. j := indexRabinKarp(s[i:], substr) if j < 0 { return -1 } return i + j } } return -1 }
internel/bytealg中:
MaxLen is the maximum length of the string to be searched for (argument b) in Index.
main.go:5:2: use of internal package internal/bytealg not allowed
想看一下bytealg.Maxlen等于多少,但是go build 后报错,说internal/bytealg不允许用
在internel包搜了一下MaxLen
如是,MaxLen于CPU有关。
package bytealg import "internal/cpu" const MaxBruteForce = 64 func init() { if cpu.X86.HasAVX2 { MaxLen = 63 } else { MaxLen = 31 } }
cpu.X86.HasAVS2是个啥?来看一下cpu.X86.HasAVX2
X86.HasAVX = isSet(ecx1, cpuid_AVX) && osSupportsAV
看一下isSet()
func isSet(hwc uint32, value uint32) bool { return hwc&value != 0 }
// cpuid is implemented in cpu_x86.s. func cpuid(eaxArg, ecxArg uint32) (eax, ebx, ecx, edx uint32)
_, _, ecx1, edx1 := cpuid(1, 0)
osSupportsAVX := false // For XGETBV, OSXSAVE bit is required and sufficient. if X86.HasOSXSAVE { eax, _ := xgetbv() // Check if XMM and YMM registers have OS support. osSupportsAVX = isSet(eax, 1<<1) && isSet(eax, 1<<2) }
。。。 涉及cpu硬件相关的了。。。。
回到strings.Index(),go on
虽然bytealg.MaxLen不知道是多少,但是但是从case语句不难看出,bytealg.MaxLen是一个可能要比substr的长度小的值,如果substr的确比bytealg.MaxLen小,则执行case n <= bytealg.MaxLen ,否则跳出case。
直接看case 几种情况都不满足的块
c0 := substr[0] // 获取substr的第一个字符 c1 := substr[1] // 第二个 i := 0 t := len(s) - n + 1 // t是s的长度减substr的长度 + 1 ,,,啧啧啧 fails := 0 for i < t { // 进入循环 if s[i] != c0 { // 如果substr的头 不等于 s[i] o := IndexByte(s[i:t], c0) // 直接将substr的头放在s的slice中判断 if o < 0 { // 不存在,直接返回-1 return -1 } // substr的头存在于 s[i]剩下的部分 。那直接看substr的第二个字符存不存在于 s[i+o]中, i += o } if s[i+1] == c1 && s[i:i+n] == substr { // 恩,如果substr的头等于s[i] 直接看substr的第二个字符等不等于s[i+1] // 并且判断s的slices[i:i+n]和substr相等不,如果相等,那么substr就存在于s中了,位置是 i return i } // 其他情况,i++ ,在for的判定条件下继续循环。失败次数+1, i++ fails++ if fails >= 4+i>>4 && i < t { 如果失败次数大于等于 4+i 得到二进制数右移四位并且i < t , // 得看一下indexrabinKarp 是个啥? //不难看出,这块是针对于失败次数比较多的时候执行的。 // See comment in ../bytes/bytes_generic.go. j := indexRabinKarp(s[i:], substr) if j < 0 { return -1 } return i + j } } // 如果循环执行完了,到这儿了,说明substr不存在于s中,返回-1 return -1
indexRabinKarp()
看一下indexRabinKarp() 吧!
Rabin-Karp是个啥?查了一下。
原来rabinkarp是一种字符串查找算法,看看吧!想必你已经知道Rabin-Karp了,直接跳到下一个目录吧。
Rabin-Karp Algorithm-WikiPediafunc indexRabinKarp(s, substr string) int { // Rabin-Karp search hashss, pow := hashStr(substr) // hashStr是个啥? n := len(substr) var h uint32 for i := 0; i < n; i++ { // 当 0 < i < n 时 循环,得到h,执行下一块的if判断 h = h*primeRK + uint32(s[i]) } if h == hashss && s[:n] == substr { // 如果 判断substr是不是就是紧挨这s的头对齐的时候并且相等的,如果是,index = 0,返回0 return 0 } for i := n; i < len(s); { // 如果 substr和s的头对齐之后不相等,则继续循环, 判断下。从i = n开始判断 h *= primeRK h += uint32(s[i]) h -= pow * uint32(s[i-n]) i++ if h == hashss && s[i-n:i] == substr { return i - n } } return -1 }
hashStr
hashStr()
// primeRK is the prime base used in Rabin-Karp algorithm. const primeRK = 16777619 // 这是一个质数 // hashStr returns the hash and the appropriate multiplicative // factor for use in Rabin-Karp algorithm. func hashStr(sep string) (uint32, uint32) { hash := uint32(0) for i := 0; i < len(sep); i++ { hash = hash*primeRK + uint32(sep[i]) // hash 是循环len(sep)次的 这串操作的int32型的数 //假设len(sep) = 4 //i = 0: hash = uint32(sep[0]) //i = 1: hash = uint32(sep[0])* primeRK + uint32(sep[1]) //... } var pow, sq uint32 = 1, primeRK for i := len(sep); i > 0; i >>= 1 { i是seq的长度,执行一次循环体之后,i = i + i右移一位(二进制), // 等于 i = i + floor(i/2) (十进制,) if i&1 != 0 { pow *= sq // 如果i就是1 了 pow = pow * sq } sq *= sq // i不是1,sq = sq*sq } // 假设len(sep) = 4 // i = 4, sq = sq^2 // i = 2, sq = sq^4 // i = 1, pow = pow*sq = sq = sq^4 // 假设 len(sep) = 5 // i = 5, sq = sq^2 ,5的二进制101 >> 1 = 10 // i = 2, sq = sq^4 // i = 1, pow = sq = sq^4 ,还是sq^len(sep) return hash, pow 输入一个字符串,返回俩unint值 }
Rabin-Karp算法就是 为了避免挨个字符对文本s和substr进行比较,可以尝试一次性判断两者是否相等。因此,我们需要一个好的哈希函数(hash function)。通过哈希函数,可以算出代匹配字符串substr的哈希值,然后将它和文本中的s的切片s[x:y]的哈希值进行比较。
比如原字符串为: AABXYXABXZ
我的substr为:ABX
先算出ABX 的hash,然后按照substr的长度算AAB的hash,比一下,再算ABX的hash比一下,再算BXY的hash比一下,再算XYX的hash比一下,如果目标字符串和原字符串的hash比的结果一致,还得再把目标字符串和原字符串的字符串值比一下,因为不好的hash函数可能会有hash冲突。
以上所述就是小编给大家介绍的《[Golang] 源码探究:strings》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Prometheus: Up & Running
Brian Brazil / O'Reilly Media / 2018-7-9 / USD 49.99
Get up to speed with Prometheus, the metrics-based monitoring system used by tens of thousands of organizations in production. This practical guide provides application developers, sysadmins, and DevO......一起来看看 《Prometheus: Up & Running》 这本书的介绍吧!