Como concatenar com eficiência strings
-
21-09-2019 - |
Pergunta
Em Go, um string
é um tipo primitivo, o que significa que é somente leitura e toda manipulação dele criará uma nova string.
Então, se eu quiser concatenar seqüências muitas vezes sem saber a duração da sequência resultante, qual é a melhor maneira de fazê -lo?
A maneira ingênua seria:
s := ""
for i := 0; i < 1000; i++ {
s += getShortStringFromSomewhere()
}
return s
Mas isso não parece muito eficiente.
Solução
Nota adicionada em 2018
De Go 1.10, existe um strings.Builder
modelo, Por favor, dê uma olhada nesta resposta para mais detalhes.
Resposta pré-201x
A melhor maneira é usar o bytes
pacote. Tem um Buffer
tipo que implementa io.Writer
.
package main
import (
"bytes"
"fmt"
)
func main() {
var buffer bytes.Buffer
for i := 0; i < 1000; i++ {
buffer.WriteString("a")
}
fmt.Println(buffer.String())
}
Isso faz isso no tempo O (n).
Outras dicas
A maneira mais eficiente de concatenar strings é usar a função incorporada copy
. Nos meus testes, essa abordagem é ~ 3x mais rápida do que usar bytes.Buffer
e muito mais rápido (~ 12.000x) do que usar o operador +
. Além disso, ele usa menos memória.
Eu criei um caso de teste Para provar isso e aqui estão os resultados:
BenchmarkConcat 1000000 64497 ns/op 502018 B/op 0 allocs/op
BenchmarkBuffer 100000000 15.5 ns/op 2 B/op 0 allocs/op
BenchmarkCopy 500000000 5.39 ns/op 0 B/op 0 allocs/op
Abaixo está o código para teste:
package main
import (
"bytes"
"strings"
"testing"
)
func BenchmarkConcat(b *testing.B) {
var str string
for n := 0; n < b.N; n++ {
str += "x"
}
b.StopTimer()
if s := strings.Repeat("x", b.N); str != s {
b.Errorf("unexpected result; got=%s, want=%s", str, s)
}
}
func BenchmarkBuffer(b *testing.B) {
var buffer bytes.Buffer
for n := 0; n < b.N; n++ {
buffer.WriteString("x")
}
b.StopTimer()
if s := strings.Repeat("x", b.N); buffer.String() != s {
b.Errorf("unexpected result; got=%s, want=%s", buffer.String(), s)
}
}
func BenchmarkCopy(b *testing.B) {
bs := make([]byte, b.N)
bl := 0
b.ResetTimer()
for n := 0; n < b.N; n++ {
bl += copy(bs[bl:], "x")
}
b.StopTimer()
if s := strings.Repeat("x", b.N); string(bs) != s {
b.Errorf("unexpected result; got=%s, want=%s", string(bs), s)
}
}
// Go 1.10
func BenchmarkStringBuilder(b *testing.B) {
var strBuilder strings.Builder
b.ResetTimer()
for n := 0; n < b.N; n++ {
strBuilder.WriteString("x")
}
b.StopTimer()
if s := strings.Repeat("x", b.N); strBuilder.String() != s {
b.Errorf("unexpected result; got=%s, want=%s", strBuilder.String(), s)
}
}
Começando com Go 1.10, há um strings.Builder
, aqui.
Um construtor é usado para criar com eficiência uma string usando métodos de gravação. Minimiza a cópia da memória. O valor zero está pronto para uso.
Uso:
É quase o mesmo com bytes.Buffer
.
package main
import (
"strings"
"fmt"
)
func main() {
var str strings.Builder
for i := 0; i < 1000; i++ {
str.WriteString("a")
}
fmt.Println(str.String())
}
Observação: Não copie um valor de StringBuilder, pois ele armazena em cache os dados subjacentes. Se você deseja compartilhar um valor de stringbuilder, use ponteiros.
Métodos e interfaces de StringBuilder que ele suporta:
Seus métodos estão sendo implementados com as interfaces existentes em mente para que você possa mudar para o novo construtor facilmente em seu código.
- Crescer (int) -> bytes.Buffer#Grow
- Len () int -> Bytes.Buffer#Len
- Redefinir() -> Bytes.Buffer#Redefinir
- String () string -> fmt.stringer
- Escreva ([] byte) (int, erro) -> io.writer
- Erro de WriteByte (byte) -> io.bytewriter
- Writerune (Rune) (Int, Erro) -> bufio.writer#writerune - Bytes.Buffer#Writerune
- Writestring (String) (int, erro) -> io.stringwriter
Uso de valor zero:
var buf strings.Builder
Diferenças de Bytes.Buffer:
Só pode crescer ou redefinir.
Dentro
bytes.Buffer
, pode -se acessar os bytes subjacentes como este:(*Buffer).Bytes()
;strings.Builder
impede esse problema. Às vezes, isso não é um problema e, em vez dissoio.Reader
etc).Ele também possui um mecanismo de copyCheck embutido que impede a copiá-lo acidentalmente (
func (b *Builder) copyCheck() { ... }
).
Confira seu código -fonte aqui.
Existe uma função de biblioteca no pacote de strings chamado Join
:
http://golang.org/pkg/strings/#join
Uma olhada no código de Join
Mostra uma abordagem semelhante à função Append Kinopiko escreveu: https://golang.org/src/strings/strings.go#l420
Uso:
import (
"fmt";
"strings";
)
func main() {
s := []string{"this", "is", "a", "joined", "string\n"};
fmt.Printf(strings.Join(s, " "));
}
$ ./test.bin
this is a joined string
Acabei de comparar a resposta superior postada acima em meu próprio código (uma caminhada de árvore recursiva) e o operador de concat simples é realmente mais rápido que o BufferString
.
func (r *record) String() string {
buffer := bytes.NewBufferString("");
fmt.Fprint(buffer,"(",r.name,"[")
for i := 0; i < len(r.subs); i++ {
fmt.Fprint(buffer,"\t",r.subs[i])
}
fmt.Fprint(buffer,"]",r.size,")\n")
return buffer.String()
}
Isso levou 0,81 segundos, enquanto o seguinte código:
func (r *record) String() string {
s := "(\"" + r.name + "\" ["
for i := 0; i < len(r.subs); i++ {
s += r.subs[i].String()
}
s += "] " + strconv.FormatInt(r.size,10) + ")\n"
return s
}
levou apenas 0,61 segundos. Provavelmente isso se deve à sobrecarga de criar o novo BufferString
.
Atualizar: Eu também comparei o join
função e funcionou em 0,54 segundos.
func (r *record) String() string {
var parts []string
parts = append(parts, "(\"", r.name, "\" [" )
for i := 0; i < len(r.subs); i++ {
parts = append(parts, r.subs[i].String())
}
parts = append(parts, strconv.FormatInt(r.size,10), ")\n")
return strings.Join(parts,"")
}
Você pode criar uma grande fatia de bytes e copiar os bytes das cordas curtas usando fatias de string. Há uma função dada em "Go Effecting":
func Append(slice, data[]byte) []byte {
l := len(slice);
if l + len(data) > cap(slice) { // reallocate
// Allocate double what's needed, for future growth.
newSlice := make([]byte, (l+len(data))*2);
// Copy data (could use bytes.Copy()).
for i, c := range slice {
newSlice[i] = c
}
slice = newSlice;
}
slice = slice[0:l+len(data)];
for i, c := range data {
slice[l+i] = c
}
return slice;
}
Então, quando as operações forem concluídas, use string ( )
Na grande fatia de bytes, para convertê -lo em uma string novamente.
Esta é a solução mais rápida que não exige que você conheça ou calcule o tamanho geral do buffer primeiro:
var data []byte
for i := 0; i < 1000; i++ {
data = append(data, getShortStringFromSomewhere()...)
}
return string(data)
Pelo meu referência, é 20% mais lento que a solução de cópia (8,1ns por anexo em vez de 6,72ns), mas ainda 55% mais rápido do que usar bytes.buffer.
package main
import (
"fmt"
)
func main() {
var str1 = "string1"
var str2 = "string2"
out := fmt.Sprintf("%s %s ",str1, str2)
fmt.Println(out)
}
Nota adicionada em 2018
De Go 1.10, existe um strings.Builder
modelo, Por favor, dê uma olhada nesta resposta para mais detalhes.
Resposta pré-201x
O código de referência de @CD1 e outras respostas estão erradas. b.N
não deve ser definido na função de referência. É definido pela ferramenta GO de teste dinamicamente para determinar se o tempo de execução do teste é estável.
Uma função de referência deve executar o mesmo teste b.N
Os tempos e o teste dentro do loop devem ser os mesmos para cada iteração. Então, eu corrigi adicionando um loop interno. Eu também adiciono benchmarks para algumas outras soluções:
package main
import (
"bytes"
"strings"
"testing"
)
const (
sss = "xfoasneobfasieongasbg"
cnt = 10000
)
var (
bbb = []byte(sss)
expected = strings.Repeat(sss, cnt)
)
func BenchmarkCopyPreAllocate(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
bs := make([]byte, cnt*len(sss))
bl := 0
for i := 0; i < cnt; i++ {
bl += copy(bs[bl:], sss)
}
result = string(bs)
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkAppendPreAllocate(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
data := make([]byte, 0, cnt*len(sss))
for i := 0; i < cnt; i++ {
data = append(data, sss...)
}
result = string(data)
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkBufferPreAllocate(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
buf := bytes.NewBuffer(make([]byte, 0, cnt*len(sss)))
for i := 0; i < cnt; i++ {
buf.WriteString(sss)
}
result = buf.String()
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkCopy(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
data := make([]byte, 0, 64) // same size as bootstrap array of bytes.Buffer
for i := 0; i < cnt; i++ {
off := len(data)
if off+len(sss) > cap(data) {
temp := make([]byte, 2*cap(data)+len(sss))
copy(temp, data)
data = temp
}
data = data[0 : off+len(sss)]
copy(data[off:], sss)
}
result = string(data)
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkAppend(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
data := make([]byte, 0, 64)
for i := 0; i < cnt; i++ {
data = append(data, sss...)
}
result = string(data)
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkBufferWrite(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
var buf bytes.Buffer
for i := 0; i < cnt; i++ {
buf.Write(bbb)
}
result = buf.String()
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkBufferWriteString(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
var buf bytes.Buffer
for i := 0; i < cnt; i++ {
buf.WriteString(sss)
}
result = buf.String()
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
func BenchmarkConcat(b *testing.B) {
var result string
for n := 0; n < b.N; n++ {
var str string
for i := 0; i < cnt; i++ {
str += sss
}
result = str
}
b.StopTimer()
if result != expected {
b.Errorf("unexpected result; got=%s, want=%s", string(result), expected)
}
}
O ambiente é OS X 10.11.6, 2,2 GHz Intel Core i7
Resultado dos testes:
BenchmarkCopyPreAllocate-8 20000 84208 ns/op 425984 B/op 2 allocs/op
BenchmarkAppendPreAllocate-8 10000 102859 ns/op 425984 B/op 2 allocs/op
BenchmarkBufferPreAllocate-8 10000 166407 ns/op 426096 B/op 3 allocs/op
BenchmarkCopy-8 10000 160923 ns/op 933152 B/op 13 allocs/op
BenchmarkAppend-8 10000 175508 ns/op 1332096 B/op 24 allocs/op
BenchmarkBufferWrite-8 10000 239886 ns/op 933266 B/op 14 allocs/op
BenchmarkBufferWriteString-8 10000 236432 ns/op 933266 B/op 14 allocs/op
BenchmarkConcat-8 10 105603419 ns/op 1086685168 B/op 10000 allocs/op
Conclusão:
CopyPreAllocate
é a maneira mais rápida;AppendPreAllocate
está bem perto do número 1, mas é mais fácil escrever o código.Concat
Tem desempenho muito ruim para o uso de velocidade e memória. Não use isso.Buffer#Write
eBuffer#WriteString
são basicamente os mesmos em velocidade, ao contrário do que @Dani-BR-BR, disse no comentário. Considerandostring
é de fato[]byte
Em Go, faz sentido.- bytes.buffer basicamente usa a mesma solução que
Copy
com manutenção de livros extras e outras coisas. Copy
eAppend
Use um tamanho de bootstrap de 64, o mesmo que bytes.bufferAppend
Use mais memória e aloces, acho que está relacionada ao algoritmo Grow que ele usa. Não está crescendo a memória tão rápido quanto bytes.buffer
Sugestão:
- Para tarefas simples, como o que o OP quer, eu usaria
Append
ouAppendPreAllocate
. É rápido o suficiente e fácil de usar. - Se precisar ler e escrever o buffer ao mesmo tempo, use
bytes.Buffer
é claro. É para isso que foi projetado.
Minha sugestão original foi
s12 := fmt.Sprint(s1,s2)
Mas acima da resposta usando Bytes.Buffer - Writestring () é a maneira mais eficiente.
Minha sugestão inicial usa reflexão e uma chave de tipo. Ver (p *pp) doPrint
e (p *pp) printArg
Não existe interface universal () para tipos básicos, como eu pensava ingenuamente.
Pelo menos, porém, sprint () internamente usa um bytes.buffer. Desta forma
`s12 := fmt.Sprint(s1,s2,s3,s4,...,s1000)`
é aceitável em termos de alocações de memória.
=> Sprint () A concatenação pode ser usada para saída rápida de depuração.
=> Caso contrário, use bytes.buffer ... Writestring
Expandindo a resposta do CD1: você pode usar append () em vez de copy (). Apênd () faz provisões cada vez maiores, custando um pouco mais de memória, mas economizando tempo. Eu adicionei Mais dois benchmarks no seu topo. Execute localmente com
go test -bench=. -benchtime=100ms
No meu thinkpad t400s, ele produz:
BenchmarkAppendEmpty 50000000 5.0 ns/op
BenchmarkAppendPrealloc 50000000 3.5 ns/op
BenchmarkCopy 20000000 10.2 ns/op
Esta é a versão real do benchmark fornecida por @CD1 (Go 1.8
, linux x86_64
) com as correções de bugs mencionados por @icza e @pickboy.
Bytes.Buffer
é apenas 7
vezes mais rápido que a concatenação direta de string via +
operador.
package performance_test
import (
"bytes"
"fmt"
"testing"
)
const (
concatSteps = 100
)
func BenchmarkConcat(b *testing.B) {
for n := 0; n < b.N; n++ {
var str string
for i := 0; i < concatSteps; i++ {
str += "x"
}
}
}
func BenchmarkBuffer(b *testing.B) {
for n := 0; n < b.N; n++ {
var buffer bytes.Buffer
for i := 0; i < concatSteps; i++ {
buffer.WriteString("x")
}
}
}
Horários:
BenchmarkConcat-4 300000 6869 ns/op
BenchmarkBuffer-4 1000000 1186 ns/op
func JoinBetween(in []string, separator string, startIndex, endIndex int) string {
if in == nil {
return ""
}
noOfItems := endIndex - startIndex
if noOfItems <= 0 {
return EMPTY
}
var builder strings.Builder
for i := startIndex; i < endIndex; i++ {
if i > startIndex {
builder.WriteString(separator)
}
builder.WriteString(in[i])
}
return builder.String()
}
Eu faço isso usando o seguinte:-
package main
import (
"fmt"
"strings"
)
func main (){
concatenation:= strings.Join([]string{"a","b","c"},"") //where second parameter is a separator.
fmt.Println(concatenation) //abc
}
package main
import (
"fmt"
)
func main() {
var str1 = "string1"
var str2 = "string2"
result := make([]byte, 0)
result = append(result, []byte(str1)...)
result = append(result, []byte(str2)...)
result = append(result, []byte(str1)...)
result = append(result, []byte(str2)...)
fmt.Println(string(result))
}
Resultado de referência com estatísticas de alocação de memória. Verifique o código de referência em Github.
Use strings.Builder para otimizar o desempenho.
go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/hechen0/goexp/exps
BenchmarkConcat-8 1000000 60213 ns/op 503992 B/op 1 allocs/op
BenchmarkBuffer-8 100000000 11.3 ns/op 2 B/op 0 allocs/op
BenchmarkCopy-8 300000000 4.76 ns/op 0 B/op 0 allocs/op
BenchmarkStringBuilder-8 1000000000 4.14 ns/op 6 B/op 0 allocs/op
PASS
ok github.com/hechen0/goexp/exps 70.071s
s := fmt.Sprintf("%s%s", []byte(s1), []byte(s2))
strings.Join()
Do pacote "Strings"
Se você tem uma incompatibilidade de tipo (como se você estiver tentando entrar em uma INT e uma string), você faz RandomType (coisa que deseja mudar)
EX:
package main
import (
"fmt"
"strings"
)
var intEX = 0
var stringEX = "hello all you "
var stringEX2 = "people in here"
func main() {
s := []string{stringEX, stringEX2}
fmt.Println(strings.Join(s, ""))
}
Resultado :
hello all you people in here