doupijin0397
doupijin0397
2018-03-13 13:26

使用bytes.Buffer在Go中实现类似于Fibonacci的字符串串联的正确方法是什么?

  • string-concatenation
  • byte
  • buffer
已采纳

I tested simple string concatenation in Go with “+” and bytes.Buffer (both “WriteString” and “Write(bytes)”. The result shows that “+” is much slower than the other two, which makes sense.

However, when I use the three ways to implement Fibonacci-like string concatenation (i.e. a, b, ab, bab, abbab, bababbab, abbabbababbab), “+” performs the best. The sample codes and the benchmarking results are shown as follows.

String “+”

func Fibonacci(n int) string {  
    FiboResult := ""
    prev_result := "a"
    next_result := "b"
    if n == 1{  
        FiboResult = "a"
    }else if n == 2 {  
        FiboResult = "b"
    }else{
        for i := 3; i <= n; i++ {
            FiboResult = prev_result + next_result
            prev_result = next_result
            next_result = FiboResult
        }
    }   
    return FiboResult
}

bytes.Buffer (WriteString)

func Fibonacci(n int) bytes.Buffer {  
    var FiboResult bytes.Buffer
    var prev_result bytes.Buffer
    prev_result.WriteString("a")
    var next_result bytes.Buffer
    next_result.WriteString("b")
    if n == 1{  
        FiboResult.WriteString("a")
    }else if n == 2 {  
        FiboResult.WriteString("b")
    }else{
        for i := 3; i <= n; i++ {
            FiboResult.Reset()
            FiboResult.WriteString(prev_result.String())
            FiboResult.WriteString(next_result.String())
            prev_result.Reset()
            prev_result.WriteString(next_result.String())
            next_result.Reset()
            next_result.WriteString(FiboResult.String())
        }
    }   
    return FiboResult
}

the benchmarking results

I believe it is the overhead of bytes.Buffer.String() that make this happen. But I could not figure out how to use bytes.Buffer correctly in this case. Or how could I modify my code to avoid the problem? Hints, sample codes, or explanations are all appreciated. Many thanks in advance!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • douzhi2012 douzhi2012 3年前

    bytes.Buffer (or the newer and faster strings.Builder) wins over simple + string concatenation if you want to append "many" values, and obtain the result once in the end, because intermediate allocations are not needed compared to using + multiple times.

    And you are not using bytes.Buffer this way: you just write one string into it, and you obtain its content and you reset it. That's just a roundtrip which turns out to be an overhead.

    The problem here is that generating the Fibonacci string you are seeking, that requires prepending text to the buffer, not appending to it. And bytes.Buffer only supports appending to it, so using it like this is not a good fit at all.

    Generating reverse with bytes.Buffer

    Note that a prepend operation is basically an append operation if you generate the reverse of a string. Which means if we first would generate the reverse of the result, we could use bytes.Buffer to perform an append when otherwise a prepend would be needed. Of course the appended string would have to also be the reverse of what otherwise would be prepended.

    And of course when we're done, we have to reverse the result to get what we originally wanted.

    Also note that when building result in an iterative way, the successive intermediate result is the concatenation of the previous and the one before that. So to obtain the nth result, we can simply append the substring of what we already have! This is a nice optimization.

    Here's how it would look like:

    func FibonacciReverseBuf(n int) string {
        switch n {
        case 0:
            return ""
        case 1:
            return "a"
        case 2:
            return "b"
        }
    
        prev, prev2 := 1, 1
    
        buf := bytes.NewBufferString("ba")
    
        for i := 3; i < n; i++ {
            buf.Write(buf.Bytes()[:buf.Len()-prev2])
            prev2, prev = prev, prev+prev2
        }
    
        // Reverse
        b := buf.Bytes()
        for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
            b[i], b[j] = b[j], b[i]
        }
    
        return string(b)
    }
    

    Generating reverse with []byte and append()

    Also note that since we're only appending, we can just as easily use a []byte and use the builtin append() function:

    func FibonacciReverse(n int) string {
        switch n {
        case 0:
            return ""
        case 1:
            return "a"
        case 2:
            return "b"
        }
    
        prev, prev2 := 1, 1
    
        b := []byte("ba")
    
        for i := 3; i < n; i++ {
            b = append(b, b[:len(b)-prev2]...)
            prev2, prev = prev, prev+prev2
        }
    
        // Reverse
        for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
            b[i], b[j] = b[j], b[i]
        }
    
        return string(b)
    }
    

    Preallocating and using copy() in a single []byte

    Still, using append() may cause reallocations, because we don't know how big the buffer (the result) will be. So we start with a small buffer, and append() will increase it as needed. Also append() requires slice value (slice header) assignments. And we also have to reverse the result.

    A much faster solution would be to get rid of those cons.

    First let's calculate how big the result will be (this is essentially calculating the Fibonacci numbers), and allocate the required byte slice in one step.

    If we do so, we can do the "prepend" operations by copying parts of our buffer (which is a []byte) to specific positions. So no append(), no reallocations, no reversing.

    This is how it will look like:

    func Fibonacci(n int) string {
        switch n {
        case 0:
            return ""
        case 1:
            return "a"
        case 2:
            return "b"
        }
    
        fibs := make([]int, n)
        fibs[0], fibs[1] = 1, 1
        for i := 2; i < n; i++ {
            fibs[i] = fibs[i-1] + fibs[i-2]
        }
    
        l := fibs[n-1]
        b := make([]byte, l)
        b[l-2], b[l-1] = 'a', 'b'
        for i := 3; i < n; i++ {
            copy(b[l-fibs[i]:], b[l-fibs[i-2]:])
        }
    
        return string(b)
    }
    

    Testing the output

    To test if the above functions give the result we expect them to give, we may use the following testing function:

    func TestFibonacci(t *testing.T) {
        cases := []struct {
            n   int
            exp string
        }{
            {0, ""},
            {1, "a"},
            {2, "b"},
            {3, "ab"},
            {4, "bab"},
            {5, "abbab"},
            {6, "bababbab"},
            {7, "abbabbababbab"},
        }
    
        funcs := []struct {
            name string
            f    func(int) string
        }{
            {"FibonacciReverseBuf", FibonacciReverseBuf},
            {"FibonacciReverse", FibonacciReverse},
            {"Fibonacci", Fibonacci},
        }
    
        for _, c := range cases {
            for _, f := range funcs {
                if got := f.f(c.n); got != c.exp {
                    t.Errorf("%s: Expected: %s, got: %s, n: %d",
                        f.name, c.exp, got, c.n)
                }
            }
        }
    }
    

    Benchmark results

    Benchmarking with n = 20:

    BenchmarkFibonacciReverseBuf-4   200000   10739 ns/op    18024 B/op   10 allocs/op
    BenchmarkFibonacciReverse-4      100000   13208 ns/op    28864 B/op   10 allocs/op
    BenchmarkFibonacci-4             500000    3383 ns/op    13728 B/op    3 allocs/op
    BenchmarkPeterSO-4               300000    4417 ns/op    13568 B/op    2 allocs/op
    BenchmarkPlus-4                  200000    6072 ns/op    18832 B/op   18 allocs/op
    BenchmarkBuffer-4                 50000   29608 ns/op    90256 B/op   60 allocs/op
    

    We can see that this use of bytes.Buffer was much better than yours. Still, using concatenation was faster, because there aren't many concatenations here, they are small ones, and that doesn't require reversing in the end.

    On the other hand my Fibonacci() solution outperformed all other presented solutions.

    点赞 评论 复制链接分享
  • dongnuo3749 dongnuo3749 3年前

    In Go, use the testing package for benchmarks.

    Write reasonably efficient Go functions. Don't perform unnecessary conversions. Minimize allocations and copies. And so on. Allow for non-ASCII characters, for example Chinese characters. Allow for strings of more than one character. Consider using a byte slice. For example,

    func fibonacciN(n int) uint64 {
        f := uint64(0)
        a, b := uint64(0), uint64(1)
        for i := 0; i < n; i++ {
            f, a, b = a, b, a+b
            if a > b {
                break
            }
        }
        return f
    }
    
    func Fibonacci(a, b string, n int) string {
        if n < 0 {
            n = 0
        }
        switch n {
        case 0:
            return ""
        case 1:
            return a
        case 2:
            return b
        }
        f := make([]byte, len(a)*int(fibonacciN(n-1))+len(b)*int(fibonacciN(n)))
        ab := a + b
        copy(f[len(f)-len(ab):], ab)
        for i := 4; i <= n; i++ {
            end := len(f) - (len(a)*int(fibonacciN(i-3)) + len(b)*int(fibonacciN(i-2)))
            start := len(f) - (len(a)*int(fibonacciN(i-1)) + len(b)*int(fibonacciN(i)))
            copy(f[start:end], f[end:])
        }
        return string(f)
    }
    

    Benchmark functions. For example, with n = 20,

    $ go test fib_test.go -bench=. -benchmem
    goos: linux
    goarch: amd64
    BenchmarkPeterSO-8    1000000     1851 ns/op    13568 B/op     2 allocs/op
    BenchmarkPlus-8        500000     2493 ns/op    18832 B/op    18 allocs/op
    BenchmarkBuffer-8      100000    12773 ns/op    90256 B/op    60 allocs/op
    PASS
    $ 
    

    fib_test.go:

    package main
    
    import (
        "bytes"
        "testing"
    )
    
    var benchN = 20
    
    func fibonacciN(n int) uint64 {
        f := uint64(0)
        a, b := uint64(0), uint64(1)
        for i := 0; i < n; i++ {
            f, a, b = a, b, a+b
            if a > b {
                break
            }
        }
        return f
    }
    
    func FibonacciPeterSO(a, b string, n int) string {
        if n < 0 {
            n = 0
        }
        switch n {
        case 0:
            return ""
        case 1:
            return a
        case 2:
            return b
        }
        f := make([]byte, len(a)*int(fibonacciN(n-1))+len(b)*int(fibonacciN(n)))
        ab := a + b
        copy(f[len(f)-len(ab):], ab)
        for i := 4; i <= n; i++ {
            end := len(f) - (len(a)*int(fibonacciN(i-3)) + len(b)*int(fibonacciN(i-2)))
            start := len(f) - (len(a)*int(fibonacciN(i-1)) + len(b)*int(fibonacciN(i)))
            copy(f[start:end], f[end:])
        }
        return string(f)
    }
    
    func BenchmarkPeterSO(b *testing.B) {
        for i := 0; i < b.N; i++ {
            FibonacciPeterSO("a", "b", benchN)
        }
    }
    
    func FibonacciPlus(n int) string {
        FiboResult := ""
        prev_result := "a"
        next_result := "b"
        if n == 1 {
            FiboResult = "a"
        } else if n == 2 {
            FiboResult = "b"
        } else {
            for i := 3; i <= n; i++ {
                FiboResult = prev_result + next_result
                prev_result = next_result
                next_result = FiboResult
            }
        }
        return FiboResult
    }
    
    func BenchmarkPlus(b *testing.B) {
        for i := 0; i < b.N; i++ {
            FibonacciPlus(benchN)
        }
    }
    
    func FibonacciBuffer(n int) bytes.Buffer {
        var FiboResult bytes.Buffer
        var prev_result bytes.Buffer
        prev_result.WriteString("a")
        var next_result bytes.Buffer
        next_result.WriteString("b")
        if n == 1 {
            FiboResult.WriteString("a")
        } else if n == 2 {
            FiboResult.WriteString("b")
        } else {
            for i := 3; i <= n; i++ {
                FiboResult.Reset()
                FiboResult.WriteString(prev_result.String())
                FiboResult.WriteString(next_result.String())
                prev_result.Reset()
                prev_result.WriteString(next_result.String())
                next_result.Reset()
                next_result.WriteString(FiboResult.String())
            }
        }
        return FiboResult
    }
    
    func BenchmarkBuffer(b *testing.B) {
        for i := 0; i < b.N; i++ {
            FibonacciBuffer(benchN)
        }
    }
    
    var testN = benchN
    
    func TestPeterSO(t *testing.T) {
        for n := 0; n <= testN; n++ {
            got := FibonacciPeterSO("a", "b", n)
            want := FibonacciPlus(n)
            if want != got {
                t.Errorf("want: %s got: %s", want, got)
            }
        }
    }
    
    点赞 评论 复制链接分享