在 Go 中使用 bytes.Buffer 实现类斐波那契字符串连接的正确方法是什么？
What is the correct way of using bytes.Buffer to implement Fibonacci-like string concatenation in Go?
我用“+”和bytes.Buffer（“WriteString”和“Write(bytes)”测试了Go中的简单字符串连接。结果显示“+”慢得多比其他两个，这是有道理的。
然而，当我使用这三种方式来实现类似斐波那契的字符串连接时（即 a、b、ab、bab、abbab、bababbab、abbabbababbab），“+”表现最好。示例代码和基准测试结果如下。
字符串“+”
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 (写入字符串)
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
我相信是 bytes.Buffer.String() 的开销让这一切发生了。但是在这种情况下我无法弄清楚如何正确使用 bytes.Buffer 。或者我怎样才能修改我的代码来避免这个问题？提示、示例代码或解释都很受欢迎。非常感谢！
在 Go 中，使用 testing 包进行基准测试。
编写相当高效的 Go 函数。不要执行不必要的转换。最小化分配和副本。等等。允许 non-ASCII 个字符，例如中文字符。允许超过一个字符的字符串。考虑使用字节片。例如，
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)
}
基准函数。例如，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)
}
}
}
bytes.Buffer (or the newer and faster strings.Builder) 如果您想追加 "many" 值，则胜过简单的 + 字符串连接，并在最后获得一次结果，因为与多次使用 +。
并且您没有以这种方式使用 bytes.Buffer：您只需将一个 string 写入其中，然后获取其内容并重置它。这只是一个往返，结果是开销。
这里的问题是生成您正在寻找的 Fibonacci 字符串，这需要 prepending 文本到缓冲区，而不是 appending .而且bytes.Buffer只支持附加到它，所以这样使用它根本不合适。
使用 bytes.Buffer
生成反向
请注意，如果生成字符串的反转，前置操作基本上就是追加操作。这意味着如果我们首先生成结果的反转，我们可以使用 bytes.Buffer 来执行附加，否则将需要前置。当然，附加的字符串也必须与其他方式相反。
当然，当我们完成后，我们必须反转结果以获得我们最初想要的结果。
另请注意，当以迭代方式构建结果时，连续的中间结果是前一个和前一个的串联。所以要获得第 n 个结果，我们可以简单地附加我们已有的子串！这是一个很好的优化。
这是它的样子：
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)
}
使用 []byte 和 append()
生成反向
另请注意，由于我们只是追加，我们可以轻松地使用 []byte 并使用内置 append() 函数：
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)
}
在单个 []byte
中预分配和使用 copy()
不过，使用 append() 可能会导致重新分配，因为我们不知道缓冲区（结果）有多大。所以我们从一个小缓冲区开始，append() 会根据需要增加它。另外 append() 需要切片值（切片头）赋值。我们还必须扭转结果。
一个更快的解决方案是摆脱这些缺点。
首先我们计算一下结果有多大（本质上就是计算斐波那契数列），一步分配需要的字节片。
如果我们这样做，我们可以通过将缓冲区（[]byte）的部分内容复制到特定位置来执行 "prepend" 操作。所以没有 append()，没有重新分配，没有逆转。
这是它的样子：
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)
}
测试输出
为了测试上面的函数是否给出了我们期望的结果，我们可以使用下面的测试函数：
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)
}
}
}
}
基准测试结果
使用 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
我们可以看到 bytes.Buffer 的这种用法比你的要好得多。尽管如此，使用连接还是更快，因为这里的连接不多，它们很小，最后不需要反转。
另一方面，我的 Fibonacci() 解决方案优于所有其他提出的解决方案。
我用“+”和bytes.Buffer（“WriteString”和“Write(bytes)”测试了Go中的简单字符串连接。结果显示“+”慢得多比其他两个，这是有道理的。
然而，当我使用这三种方式来实现类似斐波那契的字符串连接时（即 a、b、ab、bab、abbab、bababbab、abbabbababbab），“+”表现最好。示例代码和基准测试结果如下。
字符串“+”
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 (写入字符串)
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
我相信是 bytes.Buffer.String() 的开销让这一切发生了。但是在这种情况下我无法弄清楚如何正确使用 bytes.Buffer 。或者我怎样才能修改我的代码来避免这个问题？提示、示例代码或解释都很受欢迎。非常感谢！
在 Go 中，使用 testing 包进行基准测试。
编写相当高效的 Go 函数。不要执行不必要的转换。最小化分配和副本。等等。允许 non-ASCII 个字符，例如中文字符。允许超过一个字符的字符串。考虑使用字节片。例如，
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)
}
基准函数。例如，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)
}
}
}
bytes.Buffer (or the newer and faster strings.Builder) 如果您想追加 "many" 值，则胜过简单的 + 字符串连接，并在最后获得一次结果，因为与多次使用 +。
并且您没有以这种方式使用 bytes.Buffer：您只需将一个 string 写入其中，然后获取其内容并重置它。这只是一个往返，结果是开销。
这里的问题是生成您正在寻找的 Fibonacci 字符串，这需要 prepending 文本到缓冲区，而不是 appending .而且bytes.Buffer只支持附加到它，所以这样使用它根本不合适。
使用 bytes.Buffer
生成反向
请注意，如果生成字符串的反转，前置操作基本上就是追加操作。这意味着如果我们首先生成结果的反转，我们可以使用 bytes.Buffer 来执行附加，否则将需要前置。当然，附加的字符串也必须与其他方式相反。
当然，当我们完成后，我们必须反转结果以获得我们最初想要的结果。
另请注意，当以迭代方式构建结果时，连续的中间结果是前一个和前一个的串联。所以要获得第 n 个结果，我们可以简单地附加我们已有的子串！这是一个很好的优化。
这是它的样子：
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)
}
使用 []byte 和 append()
生成反向
另请注意，由于我们只是追加，我们可以轻松地使用 []byte 并使用内置 append() 函数：
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)
}
在单个 []byte
中预分配和使用 copy()
不过，使用 append() 可能会导致重新分配，因为我们不知道缓冲区（结果）有多大。所以我们从一个小缓冲区开始，append() 会根据需要增加它。另外 append() 需要切片值（切片头）赋值。我们还必须扭转结果。
一个更快的解决方案是摆脱这些缺点。
首先我们计算一下结果有多大（本质上就是计算斐波那契数列），一步分配需要的字节片。
如果我们这样做，我们可以通过将缓冲区（[]byte）的部分内容复制到特定位置来执行 "prepend" 操作。所以没有 append()，没有重新分配，没有逆转。
这是它的样子：
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)
}
测试输出
为了测试上面的函数是否给出了我们期望的结果，我们可以使用下面的测试函数：
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)
}
}
}
}
基准测试结果
使用 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
我们可以看到 bytes.Buffer 的这种用法比你的要好得多。尽管如此，使用连接还是更快，因为这里的连接不多，它们很小，最后不需要反转。
另一方面，我的 Fibonacci() 解决方案优于所有其他提出的解决方案。