Wie erzeuge ich in Go eine zufällige Zeichenfolge fester Länge?

Problem

Ich möchte nur eine zufällige Zeichenfolge (Groß- oder Kleinbuchstaben). ), keine Zahlen, in Go. Was ist der schnellste und einfachste Weg, dies zu tun?

Antworten

Die Frage sucht nach dem „schnellsten und einfachsten“ Ansatz. Pauls Antwort bietet eine einfache Technik. Betrachten wir jedoch auch den „schnellsten“ Aspekt. Wir werden unseren Code iterativ verfeinern und zu einer optimierten Lösung gelangen.

I. Verbesserungen

1. Genesis (Runen)

Die erste Lösung, die wir optimieren werden, ist:

import (
    "math/rand"
    "time"
)

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}

2. Bytes

Wenn die für die Zufallszeichenfolge verwendeten Zeichen auf englische Groß- und Kleinbuchstaben beschränkt sind, können wir mit Bytes arbeiten, da die Buchstaben des englischen Alphabets 1:1 Bytes in der UTF-8-Kodierung zugeordnet werden ( welches Go zum Speichern von Zeichenfolgen verwendet).

So können wir Folgendes ersetzen:

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

mit:

var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

Oder besser Yet:

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

Dies ist eine erhebliche Verbesserung, da wir jetzt eine Konstante verwenden können (Go unterstützt String-Konstanten, aber keine Slice-Konstanten). Darüber hinaus ist auch der Ausdruck len(letters) konstant.

3. Rest

Vorherige Lösungen ermittelten eine Zufallszahl für einen Buchstaben durch den Aufruf von rand.Intn() (der an Rand.Intn() und weiter an Rand.Int31n() delegiert).

Dies ist langsamer als die Verwendung von rand.Int63(), das eine Zufallszahl mit 63 Zufallsbits erzeugt.

Wir können also einfach aufrufen rand.Int63() und verwenden Sie den Rest nach der Division durch len(letters):

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letters[rand.Int63() % int64(len(letters))]
    }
    return string(b)
}

Dies ist schneller und behält gleichzeitig eine gleiche Wahrscheinlichkeitsverteilung aller Buchstaben bei (obwohl die Verzerrung vernachlässigbar ist, ist die Anzahl der Buchstaben 52 viel kleiner als 1

4. Maskierung

Wir können eine gleichmäßige Verteilung der Buchstaben aufrechterhalten, indem wir nur die niedrigsten Bits der Zufallszahl verwenden, die ausreichen, um die Anzahl der Buchstaben darzustellen. Für 52 Buchstaben werden 6 Bit benötigt: 52 = 110100b. Daher verwenden wir nur die niedrigsten 6 Bits der von rand.Int63() zurückgegebenen Zahl.

Wir „akzeptieren“ die Zahl auch nur, wenn sie im Bereich 0..len(letterBytes)-1 liegt . Wenn die niedrigsten Bits größer sind, verwerfen wir und fordern eine neue Zahl an.

const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1
5. Maskierung verbessert
Die vorherige Lösung verwendet nur die niedrigsten 6 Bits der 63 Zufallsbits von rand.Int63(). Dies ist ineffizient, da das Erhalten der Zufallsbits der langsamste Teil unseres Algorithmus ist.
Da wir 52 Buchstaben haben, kodieren 6 Bits einen Buchstabenindex. Die 63 Zufallsbits können 63/6 = 10 verschiedene Buchstabenindizes bezeichnen. Lassen Sie uns alle 10 verwenden:
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx >= letterIdxBits
        remain--
    }
    return string(b)
}
6. Quelle
Maskierung verbessert ist ziemlich effizient. Betrachten wir einen anderen Aspekt: ​​die Quelle von Zufallszahlen.
Das Paket crypto/rand stellt die Funktion Read(b []byte) bereit. Dies würde jedoch die Leistung nicht verbessern, da crypto/rand einen kryptografisch sicheren Pseudozufallszahlengenerator implementiert, der langsamer ist.
Wir bleiben also beim math/rand-Paket. rand.Rand verwendet eine rand.Source als Quelle für Zufallsbits. Wir können also direkt eine rand.Source verwenden:
var src = rand.NewSource(time.Now().UnixNano())

func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx >= letterIdxBits
        remain--
    }
    return string(b)
}
7. Unter Verwendung von strings.Builder
Frühere Lösungen gaben Strings zurück, die zuerst in einem Slice erstellt wurden ([]rune in Genesis und anschließend []byte) und dann in String konvertiert wurden. Diese endgültige Konvertierung erfordert das Kopieren des Slice-Inhalts, da String-Werte unveränderlich sind.
Go 1.10 führte strings.Builder ein. Mit diesem neuen Typ können String-Inhalte ähnlich wie bytes.Buffer erstellt werden. Es verwendet intern ein []Byte und muss den Inhalt nicht kopieren, um die Zeichenfolge zu erstellen.
func RandStringBytesMaskImprSrcSB(n int) string {
    sb := strings.Builder{}
    sb.Grow(n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx >= letterIdxBits
        remain--
    }
    return sb.String()
}
8. „Imitiert“ strings.Builder mit dem Paket unsafe
strings.Builder erstellt einen String in einem internen []Byte, genau wie wir es selbst gemacht haben. Die Verwendung von strings.Builder führt also zu einem gewissen Overhead, den wir nur geändert haben, um das endgültige Kopieren zu vermeiden.
Wir können dieses Kopieren jedoch auch vermeiden, indem wir das Paket unsafe verwenden:
func RandStringBytesMaskImprSrcUnsafe(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx