共计 4329 个字符，预计需要花费 11 分钟才能阅读完成。
go strings.Builder 应用
前言
自己最近在找工作, 面试的时候有一个手撕题目, 这里题目形容如下:
问题形容
// 实现一个 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 的数据据构造如下:
// 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- 阿里云开发者社区 (aliyun.com)](https://developer.aliyun.com/…))
一下简略的应用 strings.Builder 和间接应用 string concat 的性能差距:
// 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 不容许拷贝的起因。
var b1 strings.Builder
b1.WriteString("ABC")
b2 := b1
b2.WriteString("DEF")
// illegal use of non-zero Builder copied by value在拷贝之后 Write 之类的办法和 Grow 办法会检测是否复制,, 然而如果你拷贝了之后不写数据不产生内存上的变动是不会有危险的, 再有就是 reset 之后能够失常操作了:
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 的时候判断本身地址和保留的地址是否统一就能够:
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")
}
}潜在的多线程问题
没有对多线程解决, 会导致数据失落.
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 写入的对象, 如有:
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