第 5 期 2018-05-10 线下活动 - Go 标准包阅读

参与人数: 20 人

Go 标准包阅读

Go 版本:go 1.10.1

strings

  • strings.go(进度50%)

问题清单

以下是我们在阅读过程中的一些问题,希望可以引起大家的关注,也欢迎大家提出自己的理解,最好可以给以文章总结。

重头戏:Rabin-Karp search

Rabin-Karp 算法的思想:

  1. 假设待匹配字符串的长度为M,目标字符串的长度为N(N>M);
  2. 首先计算待匹配字符串的hash值,计算目标字符串前M个字符的hash值;
  3. 比较前面计算的两个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目录有同一个父目录的包所导入。

举例说明:

TotalConn01 totalConn

time.Sleep()的实现函数在runtime包的time.go …

其他更多的使用,大家可以自行搜索 go:linkname

timeSleep

unexport01 unexport02 unexport03 unexport04 unexport05

更多相关知识,大家可点击:突破限制,访问其它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}

延伸阅读

  1. 大家一定要看这一篇文章:Rabin-Karp 算法(字符串快速查找)
  2. primes-16777619
  3. Fowler–Noll–Vo hash function
  4. FNV Hash
  5. FNV哈希算法【学习】
  6. 字符串查找算法(二)
  7. 突破限制,访问其它Go package中的私有函数
  8. How to call private functions (bind to hidden symbols) in GoLang
  9. 《深入解析 Go 之基本类型-字符串》