Question Comment concaténer efficacement les chaînes dans Go?


En Go, un string est un type primitif, ce qui signifie qu'il est en lecture seule, et chaque manipulation de celui-ci va créer une nouvelle chaîne.

Donc, si je veux concaténer des chaînes plusieurs fois sans connaître la longueur de la chaîne résultante, quelle est la meilleure façon de le faire?

La manière naïve serait:

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

mais cela ne semble pas très efficace.


520
2017-11-19 03:44


origine


Réponses:


Le meilleur moyen est d'utiliser le bytes paquet. Il a un Buffer type qui implémente 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())
}

Cela se fait en temps O (n).

Note ajoutée en 2018

De Go 1.10 il y a le cordes.Builder type, qui réalise cela encore plus efficacement (pour les cordes). L'exemple donné est succinct et facile à copier / adapter.

Ceci est analogue à la StringBuilder classe en Java.


694
2017-11-19 20:31



Le moyen le plus efficace de concaténer les chaînes est d'utiliser la fonction intégrée copy. Dans mes tests, cette approche est ~ 3x plus rapide que l'utilisation bytes.Buffer et beaucoup beaucoup plus rapide (~ 12 000 x) que d'utiliser l'opérateur +. En outre, il utilise moins de mémoire.

J'ai créé un cas de test pour le prouver et voici les résultats:

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

Voici le code pour tester:

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

237
2018-05-25 17:22



Il y a une fonction de bibliothèque dans le paquet de chaînes appelé Join: http://golang.org/pkg/strings/#Join

Un regard sur le code de Join montre une approche similaire à Append fonction Kinopiko a écrit: https://golang.org/src/strings/strings.go#L462

Usage:

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

115
2017-11-19 14:18



En commençant par Go 1.10 il y a un strings.Builder, ici.

Un générateur est utilisé pour créer efficacement une chaîne à l'aide de méthodes Write. Il minimise la copie de la mémoire. La valeur zéro est prête à l'emploi.


Usage:

C'est presque pareil avec 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())
}

Méthodes et interfaces StringBuilder prises en charge:

Ses méthodes sont implémentées avec les interfaces existantes à l'esprit afin que vous puissiez facilement passer au nouveau Builder dans votre code.


Utilisation de la valeur zéro:

var sb strings.Builder

Différences avec bytes.Buffer:

  • C'est immuable et il ne peut que grandir ou se réinitialiser.

  • Dans bytes.Buffer les octets sous-jacents peuvent s'échapper comme ceci: (*Buffer).Bytes(); strings.Builder empêche ce problème.

  • Il dispose également d'un mécanisme copyCheck à l'intérieur qui empêche la copie accidentelle (func (b *Builder) copyCheck() { ... }).


Découvrez son code source ici.


50
2017-12-13 16:57



J'ai juste évalué la meilleure réponse postée ci-dessus dans mon propre code (une marche en arbre récursive) et l'opérateur de concat est en fait plus rapide que 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()
}

Cela a pris 0.81s, alors que le code suivant:

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
} 

seulement pris 0.61s. Cela est probablement dû à la surcharge de création du nouveau BufferStrings.

Mettre à jour: J'ai également évalué la joindre fonction et il a couru en 0.54s

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

37
2018-04-29 01:15



C'est la solution la plus rapide qui ne nécessite pas vous devez connaître ou calculer la taille globale du tampon en premier:

var data []byte
for i := 0; i < 1000; i++ {
    data = append(data, getShortStringFromSomewhere()...)
}
return string(data)

Par mon référence, il est 20% plus lent que la solution de copie (8.1ns par ajouter plutôt que 6.72ns) mais toujours 55% plus rapide que d'utiliser bytes.Buffer.


19
2017-08-28 10:46



Vous pouvez créer une grande tranche d'octets et y copier les octets des chaînes courtes à l'aide de tranches de chaîne. Il y a une fonction donnée dans "Effective Go":

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;
}

Ensuite, lorsque les opérations sont terminées, utilisez string ( ) sur la grosse tranche d'octets pour le convertir en une chaîne à nouveau.


18
2017-11-19 03:57



Mise à jour 2018-04-03

À partir de Go 1.10, string.Builder est recommandé d'être un remplacement pour bytes.Buffer. Vérifier les notes de version 1.10

Un nouveau type Builder est un remplacement de bytes.Buffer pour le cas d'utilisation de l'accumulation de texte dans un résultat de chaîne. L'API Builder est un sous-ensemble restreint de bytes.Buffer qui lui permet d'éviter en toute sécurité de faire une copie des données pendant la méthode String.

============================================= ==========

Le code de référence de @ cd1 et d'autres réponses sont erronés. b.N n'est pas censé être défini dans la fonction de benchmark. Il est défini dynamiquement par l'outil de test go pour déterminer si le temps d'exécution du test est stable.

Une fonction de benchmark devrait exécuter le même test b.N les temps et le test à l'intérieur de la boucle devraient être les mêmes pour chaque itération. Donc je le répare en ajoutant une boucle interne. J'ajoute également des benchmarks pour d'autres solutions:

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

L'environnement est OS X 10.11.6, Intel Core i7 2,2 GHz

Résultats de test:

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

Conclusion:

  1. CopyPreAllocate est le moyen le plus rapide; AppendPreAllocate est assez proche du n ° 1, mais il est plus facile d'écrire le code.
  2. Concat a de très mauvaises performances à la fois pour la vitesse et l'utilisation de la mémoire. Ne l'utilisez pas.
  3. Buffer#Write et Buffer#WriteString sont fondamentalement les mêmes en vitesse, contrairement à ce que Dani-Br a dit dans le commentaire. Considérant string est en effet []byte dans Go, ça a du sens.
  4. bytes.Buffer utilise essentiellement la même solution que Copy avec une tenue de livres supplémentaire et d'autres choses.
  5. Copy et Append utiliser une taille bootstrap de 64, identique à bytes.Buffer
  6. Append utiliser plus de mémoire et d'allocs, je pense que c'est lié à l'algorithme de croissance qu'il utilise. Ce n'est pas la mémoire croissante aussi vite que bytes.Buffer

Suggestion:

  1. Pour une tâche simple comme ce que l'OP veut, j'utiliserais Append ou AppendPreAllocate. C'est assez rapide et facile à utiliser.
  2. Si vous avez besoin de lire et d'écrire le tampon en même temps, utilisez bytes.Buffer bien sûr. C'est pour ça que c'est conçu.

17
2018-04-28 08:03



package main

import (
  "fmt"
)

func main() {
    var str1 = "string1"
    var str2 = "string2"
    out := fmt.Sprintf("%s %s ",str1, str2)
    fmt.Println(out)
}

14
2018-03-06 20:35



Ma suggestion originale était

s12 := fmt.Sprint(s1,s2)

Mais ci-dessus réponse en utilisant bytes.Buffer - WriteString () est le moyen le plus efficace.

Ma suggestion initiale utilise la réflexion et un commutateur de type. Voir (p *pp) doPrint et (p *pp) printArg
Il n'y a pas d'interface universelle Stringer () pour les types de base, comme je l'avais pensé naïvement.

Au moins, Sprint () intérieurement utilise un bytes.Buffer. Ainsi

`s12 := fmt.Sprint(s1,s2,s3,s4,...,s1000)`

est acceptable en termes d'allocations de mémoire.

=> La concaténation Sprint () peut être utilisée pour une sortie de débogage rapide.
=> Sinon, utilisez bytes.Buffer ... WriteString


12
2017-07-02 12:51



Expansion de la réponse de CD1: Vous pouvez utiliser append () au lieu de copy (). append () fait des provisions anticipées toujours plus importantes, en coûtant un peu plus de mémoire, mais en gagnant du temps. J'ai ajouté deux autres benchmarks au sommet de la vôtre. Exécuter localement avec

go test -bench=. -benchtime=100ms

Sur mon thinkpad T400s il cède:

BenchmarkAppendEmpty    50000000         5.0 ns/op
BenchmarkAppendPrealloc 50000000         3.5 ns/op
BenchmarkCopy           20000000        10.2 ns/op

10
2018-01-25 02:40