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.Builderb1.WriteString("ABC")b2 := b1b2.WriteString("DEF") // illegal use of non-zero Builder copied by value

在拷贝之后Write之类的办法和Grow办法会检测是否复制,,然而如果你拷贝了之后不写数据不产生内存上的变动是不会有危险的,再有就是reset之后能够失常操作了:

var b1 strings.Builderb1.WriteString("ABC")b2 := b1fmt.Println(b2.Len())    // 3fmt.Println(b2.String()) // ABCb2.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) *Writerfmt.Fprint(w io.Writer, a …interface{}) (n int, err error)func (r *http.Request) Write(w io.Writer) error