# 使用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条回答

• `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, fibs = 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.

点赞 评论 复制链接分享
• 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)
}
}
}
``````
点赞 评论 复制链接分享