go strings.Builder 使用

前言

本人最近在找工作,面试的时候有一个手撕题目,这里题目描述如下:

问题描述

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
47
48
49
50
51
52
// 实现一个textProcessor, 要求能够将对应的文本中的tag转换为之前设置过的内容:
// 示例如下
// set_variable("name", "lixiande")
// get_text("Dear interviewer [name], welcome to our interview! ) // 应当是Dear interviewer lixiande, welcome to our interview!
// 由于最近使用go比较多,所以直接使用go实现
type TextProcessor struct {
	record map[string]string
}

func NewTextProcessor() *TextProcessor {
	return &TextProcessor{
		record: make(map[string]string),
	}
}

func (t *TextProcessor) set_variable(key, value string) {
	if _, ok := t.record[key]; ok {
		print("[warning] key exists!")
		t.record[key] = value
	} else {
		t.record[key] = value
	}
}

func (t *TextProcessor) get_text(text string) string {
	// -1:正常 0 ：[剩下来的字符串当tag，
	flag := -1
	res := ""
	tag := ""
	for _, v := range text {
		if flag == -1 {
			if v != '[' {
				res += string(v)
			} else {
				flag = 0
			}
		} else {
			if flag == 0 {
				if v != ']' {
					tag += string(v)
				} else {
					if tagStr, ok := t.record[tag]; ok {
						res += tagStr
						tag = ""
					}
					flag = -1
				}
			}
		}
	}
	return res
}

到这里基本就算做出来了,但是面试官让我分析一下时间复杂度,我下意识就说 O(n),因为只需要扫描字符串一次,以及 go map 的查找时间复杂度为 O(1)(理想情况),所以综合考虑应该是 O(n).但是我大意了,这里res += string(v)实际上有一定的时间复杂度开销,在 go 里面 string 的扩容实际上和 slice 是类似的,O(n)的时间复杂度.那么有什么方法优化呢?我作为老 javaer,自然是知道 java 里面的 stringBuilder,但是不知道 golang 的 stringBuilder 的实现,学习了一下这里也记录一下.

Golang 的 strings.Builder

Builder 的数据据结构如下:

1
2
3
4
5
6
7
// A Builder is used to efficiently build a string using Write methods.
// It minimizes memory copying. The zero value is ready to use.
// Do not copy a non-zero Builder.
type Builder struct {
	addr *Builder // of receiver, to detect copies by value
	buf  []byte
}

很明显 StringBuilder 的最基本思路就是预先分配 buf 空间,减少由于扩容带来的时间开销.这里我们写一个简单的测试函数和[Benchmark](Golang 基准测试(Benchmark)-阿里云开发者社区 (aliyun.com))

一下简单的使用 strings.Builder 和直接使用 string concat 的性能差距:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// file: testBuilder_test.go
// 简单拼接
func stringConcat() string {
	str := ""
	for i := 0; i < 1000; i++ {
		str += strconv.Itoa(i)
	}
	return str
}
// 简单Builder测试
func stringBuild() string {
	var strBuilder strings.Builder
	for i := 0; i < 1000; i++ {
		strBuilder.WriteString(strconv.Itoa(i))
	}
	return strBuilder.String()
}
// 预分配空间
func stringBuildGrow(cap int) string {
	var strBuilder strings.Builder
	strBuilder.Grow(cap)
	for i := 0; i < 1000; i++ {
		strBuilder.WriteString(strconv.Itoa(i))
	}
	return strBuilder.String()
}

func BenchmarkStringBuild(t *testing.B) {
	for i := 0; i < 100; i++ {
		stringBuild()
	}
}
func BenchmarkStringConcat(t *testing.B) {
	for i := 0; i < 100; i++ {
		stringConcat()
	}
}
func BenchmarkStringBuildGrow(t *testing.B) {
	for i := 0; i < 100; i++ {
		stringBuildGrow(100)
	}
}
//-------string builder
// goos: windows
// goarch: amd64
// pkg: test
// cpu: AMD Ryzen 7 4800U with Radeon Graphics
// BenchmarkStringBuild-16    	1000000000	         0.002625 ns/op	       0 B/op	       0 allocs/op
// PASS
// ok  	test	0.214s
// --------string builder with grow
// goos: windows
// goarch: amd64
// pkg: test
// cpu: AMD Ryzen 7 4800U with Radeon Graphics
// BenchmarkStringBuildGrow-16    	1000000000	         0.002190 ns/op	       0 B/op	       0 allocs/op
// PASS
// ok  	test	0.215s

//-------string Concat
// goos: windows
// goarch: amd64
// pkg: test
// cpu: AMD Ryzen 7 4800U with Radeon Graphics
// BenchmarkStringConcat-16    	1000000000	         0.05458 ns/op	       0 B/op	       0 allocs/op
// PASS
// ok  	test	0.631s

很明显如果只是简单的使用 builder 的情况下,时间减少一半,如果预先 grow 会怎么样呢?每次减少不少但是实际上效果一般吗,结论就是效果很好可以直接用.

注意问题

不要拷贝 strings.Builder

strings.Builder 不推荐被拷贝。当你试图拷贝一个非空的 strings.Builder 并写入的时候,你的程序就会崩溃。当我们拷贝了 builder 以后，同样也拷贝了其 slice 的指针。但是它仍然指向同一个旧的数组。当你对源 builder 或者拷贝后的 builder 写入的时候，问题就产生了。另一个 builder 指向的数组内容也被改变了。这就是为什么 strings.Builder 不允许拷贝的原因。

1
2
3
4
5
var b1 strings.Builder
b1.WriteString("ABC")
b2 := b1
b2.WriteString("DEF")
// illegal use of non-zero Builder copied by value

在拷贝之后 Write 之类的方法和 Grow 方法会检测是否复制,,但是如果你拷贝了之后不写数据不发生内存上的变化是不会有风险的,再有就是 reset 之后可以正常操作了:

1
2
3
4
5
6
7
8
var b1 strings.Builder
b1.WriteString("ABC")
b2 := b1
fmt.Println(b2.Len())    // 3
fmt.Println(b2.String()) // ABC
b2.Reset()
b2.WriteString("DEF")
fmt.Println(b2.String()) // DEF

具体实现方法是保存了一个自身地址的参数,当检查 copy 的时候判断自身地址和保存的地址是否一致就可以:

1
2
3
4
5
6
7
8
9
10
11
12
func (b *Builder) copyCheck() {
	if b.addr == nil {
		// This hack works around a failing of Go's escape analysis
		// that was causing b to escape and be heap allocated.
		// See issue 23382.
		// TODO: once issue 7921 is fixed, this should be reverted to
		// just "b.addr = b".
		b.addr = (*Builder)(noescape(unsafe.Pointer(b)))
	} else if b.addr != b {
		panic("strings: illegal use of non-zero Builder copied by value")
	}
}

潜在的多线程问题

没有对多线程处理,会导致数据丢失.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func main() {
	var builder strings.Builder
	var group sync.WaitGroup
	for i := 0; i < 10; i++ {
		group.Add(1)
		go func(i int) {
			for j := 0; j < 10; j++ {
				builder.WriteString(strconv.Itoa(i))
			}
			group.Done()
		}(i)
	}
	group.Wait()
    // 预期应该有100个长度
	print(builder.Len())
	// select {}
}
// go run .\main.go
// 74
// 实际只有74个,其中有26个会由于对同一个索引写而导致丢失

io.Writer 接口

由于实现了 Write([]byte)方法因而很多情况下可以用 strings.Builder 作为 io 写入的对象,如有:

1
2
3
4
io.Copy(dst Writer, src Reader) (written int64, err error)
bufio.NewWriter(w io.Writer) *Writer
fmt.Fprint(w io.Writer, a …interface{}) (n int, err error)
func (r *http.Request) Write(w io.Writer) error