Wie man Strings in Go effizient verketten kann

Question

Im Go ist ein string ein primitiver Typ, was bedeutet, dass er schreibgeschützt ist und jede Manipulation einen neuen String erstellt.

Also, wenn ich Strings viele Male hintereinander verketten möchte, ohne die Länge des resultierenden Strings zu kennen, wie mache ich das am besten?

Der naive Ansatz wäre:

var s string
for i := 0; i < 1000; i++ {
    s += getShortStringFromSomewhere()
}
return s

aber das scheint nicht sehr effizient zu sein.

Answer 1

Neue Methode:

Ab Go 1.10 gibt es einen strings.Builder Typ, bitte werfen Sie einen Blick auf diese Antwort für weitere Details.

Alte Methode:

Verwenden Sie das bytes Paket. Es hat einen Buffer Typ, der io.Writer implementiert.

package main

import (
    "bytes"
    "fmt"
)

func main() {
    var buffer bytes.Buffer

    for i := 0; i < 1000; i++ {
        buffer.WriteString("a")
    }

    fmt.Println(buffer.String())
}

Dies geschieht in O(n) Zeit.

Answer 2

Ab Go 1.10+ gibt es strings.Builder, hier.

Ein Builder wird verwendet, um effizient einen String mit Write-Methoden zu erstellen. Es minimiert das Kopieren von Speicher. Der Nullwert ist einsatzbereit.

---

Beispiel

Es ist fast dasselbe wie mit bytes.Buffer.

package main

import (
    "strings"
    "fmt"
)

func main() {
    // NULLWERT:
    //
    // Es ist von Anfang an einsatzbereit.
    // Du musst es nicht initialisieren.
    var sb strings.Builder

    for i := 0; i < 1000; i++ {
        sb.WriteString("a")
    }

    fmt.Println(sb.String())
}

Klicke hier, um dies im Playground zu sehen.

---

Unterstützte Schnittstellen

Die Methoden von strings.Builder werden unter Berücksichtigung der vorhandenen Schnittstellen implementiert, sodass Sie einfach vom neuen Builder-Typ in Ihrem Code umschalten können.

Methodensignatur

Schnittstelle

Beschreibung

Grow(int)

bytes.Buffer

Erhöht die Kapazität des Puffers um den angegebenen Betrag. Siehe bytes.Buffer#Grow für weitere Informationen.

Len() int

bytes.Buffer

Gibt die Anzahl der Bytes im Puffer zurück. Siehe bytes.Buffer#Len für weitere Informationen.

Reset()

bytes.Buffer

Setzt den Puffer zurück, um leer zu sein. Siehe bytes.Buffer#Reset für weitere Informationen.

String() string

fmt.Stringer

Gibt den Inhalt des Puffers als String zurück. Siehe fmt.Stringer für weitere Informationen.

Write([]byte) (int, error)

io.Writer

Schreibt die gegebenen Bytes in den Puffer. Siehe io.Writer für weitere Informationen.

WriteByte(byte) error

io.ByteWriter

Schreibt das gegebene Byte in den Puffer. Siehe io.ByteWriter für weitere Informationen.

WriteRune(rune) (int, error)

bufio.Writer oder bytes.Buffer

Schreibt das gegebene Zeichen in den Puffer. Siehe bufio.Writer#WriteRune oder bytes.Buffer#WriteRune für weitere Informationen.

WriteString(string) (int, error)

io.stringWriter

Schreibt den gegebenen String in den Puffer. Siehe io.stringWriter für weitere Informationen.

---

Unterschiede zu bytes.Buffer

• Es kann nur wachsen oder zurücksetzen.
• Es hat einen integrierten copyCheck-Mechanismus, der verhindert, dass er versehentlich kopiert wird. In bytes.Buffer kann man z.B. auf die zugrunde liegenden Bytes wie folgt zugreifen: (*Buffer).Bytes(). strings.Builder verhindert dieses Problem. Manchmal ist dies jedoch kein Problem, sondern stattdessen erwünscht. Zum Beispiel: Für das Peek-Verhalten, wenn die Bytes an einen io.Reader übergeben werden usw.
• bytes.Buffer.Reset() spult vor und verwendet erneut den zugrunde liegenden Puffer, während strings.Builder.Reset() es nicht tut, es trennt den Puffer.

---

Hinweis

• Kopieren Sie keinen strings.Builder-Wert, da er die zugrunde liegenden Daten zwischenspeichert.
• Wenn Sie einen strings.Builder-Wert teilen möchten, verwenden Sie einen Zeiger darauf.

---

Schau dir den Quellcode für weitere Details an, hier.

Answer 3

Wenn Sie die Gesamtlänge des Strings kennen, den Sie vorab zuweisen werden, kann der effizienteste Weg zum Konkatenieren von Strings die Verwendung der integrierten Funktion copy sein. Wenn Sie die Gesamtlänge nicht im Voraus wissen, verwenden Sie copy nicht und lesen Sie stattdessen die anderen Antworten.

In meinen Tests ist dieser Ansatz ~3x schneller als die Verwendung von bytes.Buffer und viel, viel schneller (~12.000x) als die Verwendung des Operators +. Außerdem benötigt es weniger Speicher.

Ich habe einen Testfall erstellt, um dies zu beweisen, und hier sind die Ergebnisse:

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

---

Im Folgenden finden Sie den Code für die Tests:

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("unerwartetes Ergebnis; erhalten=%s, soll=%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("unerwartetes Ergebnis; erhalten=%s, soll=%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("unerwartetes Ergebnis; erhalten=%s, soll=%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("unerwartetes Ergebnis; erhalten=%s, soll=%s", strBuilder.String(), s)
    }
}

Answer 4

Wenn Sie einen Zeichenfolgenslice haben, den Sie effizient in eine Zeichenfolge umwandeln möchten, können Sie diesen Ansatz verwenden. Andernfalls schauen Sie sich die anderen Antworten an.

Es gibt eine Bibliotheksfunktion im Paket strings namens Join:

Ein Blick auf den Code von Join zeigt einen ähnlichen Ansatz wie die von Kinopiko geschriebene Append-Funktion: https://golang.org/src/strings/strings.go#L420

Verwendung:

import (
    "fmt";
    "strings";
)

func main() {
    s := []string{"dies", "ist", "ein", "zusammengesetzter", "String\n"};
    fmt.Printf(strings.Join(s, " "));
}

$ ./test.bin
dies ist ein zusammengesetzter String

Answer 5

Ich habe gerade die beste Antwort oben in meinem eigenen Code (ein rekursiver Baumspaziergang) benchmarkt und der einfache Konkatenationsoperator ist tatsächlich schneller als der 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()
}

Dies dauerte 0,81 Sekunden, während der folgende Code:

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
} 

nur 0,61 Sekunden dauerte. Dies liegt wahrscheinlich an den Overhead-Kosten für das Erstellen des neuen BufferString.

Update: Ich habe auch die join Funktion benchmarkt und sie lief in 0,54 Sekunden.

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,"")
}