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.
