Go 标准包阅读
基于 Go 1.10.1
strings
- strings.go(进度50%)
问题清单
以下是我们在阅读过程中的一些问题,希望可以引起大家的关注,也欢迎大家提出自己的理解,最好可以给以文章总结。
重头戏:Rabin-Karp search
Rabin-Karp 算法的思想:
- 假设待匹配字符串的长度为M,目标字符串的长度为N(N>M);
- 首先计算待匹配字符串的hash值,计算目标字符串前M个字符的hash值;
- 比较前面计算的两个hash值,比较次数N-M+1:
- 若hash值不相等,则继续计算目标字符串的下一个长度为M的字符子串的hash值
- 若hash值相同,则需要使用朴素算法再次判断是否为相同的字串
- 16777619 为什么是这个值? RK, FNV 算法
16777619 = (2^24 + 403)) - len 计算问题?是否是每次都会计算,直接拿值,不需要单独计算的;
len(string)
的获取 string 的长度问题:
涉及到 string 的结构问题。
在runtime/strings.go 中可以看到对应的 string 结构:
type stringStruct struct {
str unsafe.Pointer
len int
}
可以得到在求 string 的长度的时候,实际上是直接获取值。
在 slice 的结构体中
type slice struct {
array unsafe.Pointer
len int
cap int
}
Len 方法跟 len 长度走。
type hmap struct {
// Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and
// ../reflect/type.go. Don't change this structure without also changing that code!
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
在map的结构体重 有个 count 的统计 map 的内部数量。
- len 与 runtime 包里面的某些实现的有何区别?
func IndexByte(s string, c byte) int // …/runtime/asm_$GOARCH.s)
- strings.s
# strings.s
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// This file is here just to make the go tool happy.
*.s
文件存在的原因是 Go 在编译的时候会启用 -compile 编译器 flag ,它要求所有的函数必须包含函数体,创建一个空的汇编语言文件绕开这个限制。
- go:linkname
控制谁可以调用它。
Go 的隐藏功能
//go:noescape
//go:noinline
//go:nosplit
//go:linkname
...
其它
// +build
//go:generate
package xxx // import "xxx"
//line
其中有一些 net_linux.go 或 asm_amd64.s,Go 语言的构建工具将只在对应的平台编译这些文件。
如果在包中加入 // +build linux darwin 表示该包只在 linux 和 mac 下被编译。
而 // +build ignore 是忽略该包。
它跟 internal 有什么不同呢?
一个internal包只能被和internal目录有同一个父目录的包所导入。
举例说明:
time.Sleep()的实现函数在runtime包的time.go
…
其他更多的使用,大家可以自行搜索 go:linkname
![unexport05](https://talkgo.org/uploads/default/original/1X/60c3a7dc5f109b791627709c64e6605396ed4304.png)
更多相关知识,大家可点击:突破限制,访问其它Go package中的私有函数
- (i+16)/8 这个16,8是什么意思?怎么解读这个逻辑的呢?
// Switch to indexShortStr when IndexByte produces too many false positives.
// Too many means more that 1 error per 8 characters.
// Allow some errors in the beginning.
if fails > (i+16)/8 {
r := indexShortStr(s[i:], substr)
if r >= 0 {
return r + i
}
return -1
}
- 逻辑是什么意思呢?
// contains reports whether c is inside the set.
func (as *asciiSet) contains(c byte) bool {
return (as[c>>5] & (1 << uint(c&31))) != 0
}
- makeASCIISet
// ascii空格包括\t,\n,\v,\f,\r, ` `
var asciiSpace = [256]uint8{'\t': 1, '\n': 1, '\v': 1, '\f': 1, '\r': 1, ' ': 1}