[解決済み】Goで一定の長さのランダムな文字列を生成するには？

2022-03-25 22:36:13

質問

数字以外の文字（大文字、小文字）のみのランダムな文字列をGoで表示させたいのですが、どうすればいいですか？これを行うための最速かつ最もシンプルな方法は何ですか？

どのように解決するのですか？

ポールの解決策を提供します。 シンプル 一般的な解決策です。

を問うものである。 最も速く、最も簡単な方法です。 . を取り上げましょう。最速の部分もそうです。最終的に最速のコードに辿り着くには、反復していくことになります。各反復のベンチマークは、解答の最後にあります。

すべての解答とベンチマーク・コードは、以下のサイトにあります。囲碁プレイグラウンド . プレイグラウンドにあるコードはテストファイルであり、実行ファイルではありません。という名前のファイルに保存する必要があります。 XX_test.go で実行し

go test -bench . -benchmem

序文 :

最速のソリューションは、単にランダムな文字列が必要な場合には、最適なソリューションではありません。その場合は、Paulのソリューションが最適です。これは、パフォーマンスが重要な場合です。最初の2つのステップ( バイト と残部 ) は、許容できる妥協点かもしれません。これらは、パフォーマンスを50%ほど向上させます (正確な数値は II. ベンチマーク のセクションを参照してください)、複雑さを大幅に増加させることはありません。

とはいえ、最速の解決策を必要としない場合でも、この回答を読み通すことは冒険であり勉強になるかもしれませんね。

I. 改良点

1. ジェネシス（ルーン文字）

注意点として、私たちが改良している本来の一般的な解答はこうです。

func init() {
    rand.Seed(time.Now().UnixNano())
}

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. バイト数

ランダムな文字列を構成する文字が英語のアルファベットの大文字と小文字だけである場合、英語のアルファベットは UTF-8 エンコーディングではバイトに 1 対 1 で対応するため、バイトだけを扱うことができます（Go が文字列を格納する方法です）。

だから代わりに

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

を使うことができます。

var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

あるいはもっといい。

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

これはすでに大きな改善です。 const (そこには string 定数ですがスライス定数はありません ). 余分な利益として、式 len(letters) はまた const ! (式 len(s) が定数である場合 s は文字列定数)

その代償は？全くありません。 string は、そのバイトにインデックスを付けることができます。これは完璧で、まさに私たちが望んでいることです。

次の目的地はこんな感じです。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func RandStringBytes(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Intn(len(letterBytes))]
    }
    return string(b)
}

3. 残部

これまでの解答では、ランダムな文字を指定するために乱数を取得するために rand.Intn() に委ねる。 Rand.Intn() に委譲されます。 Rand.Int31n() .

と比べるとかなり遅いです。 rand.Int63() は63個のランダムビットを持つ乱数を生成します。

ということは、単純に rand.Int63() で割った余りを len(letterBytes) :

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

これはうまくいってかなり速いのですが、欠点はすべての文字の確率がまったく同じにならないことです（仮に rand.Int63() は63ビットの数字をすべて同じ確率で生成します）。文字数が多いので歪みは極めて小さいですが 52 よりもはるかに小さいです。 1<<63 - 1 ということで、実際には全く問題ありません。

^{この理解を容易にするために、例えば、以下の範囲の乱数が欲しいとします。
0..5
. 3つのランダムビットを使用すると、次のような数字が得られます。
0..1
の範囲より2倍の確率で
2..5
. 5個のランダムビットを使用すると、範囲内の数字
0..1
で発生します。
6/32
の確率と範囲内の数
2..5
と
5/32
の確率は、より望ましいものに近づきました。ビット数を増やすとこの影響は小さくなり、63ビットになると無視できる程度になります。}

4. マスキング

先ほどの解決策を踏まえて、乱数の最下位ビットを文字数を表すのに必要な数だけ使用することで、文字の均等配分を維持することができるのです。つまり、例えば52文字の場合、それを表現するのに必要なビットは6ビットです。 52 = 110100b . で返される数値のうち、下位6ビットのみを使用することになります。 rand.Int63() . また、文字を均等に配置するために、次の範囲に含まれる場合のみ、数字を受け入れます。 0..len(letterBytes)-1 . 最下位ビットの方が大きい場合は、それを破棄して新しい乱数を問い合わせる。

ただし、最下位ビットが len(letterBytes) よりも小さいです。 0.5 を、一般的に( 0.25 ということは、たとえそうであっても、この「まれな」ケースを繰り返せば、良い数字が見つからない可能性が低くなることを意味します。その後 n を繰り返しても、良いインデックスが得られない確率は pow(0.5, n) これはあくまで上限値です。52文字の場合、最下位6ビットが良くない確率は、わずか (64-52)/64 = 0.19 つまり、例えば10回繰り返した後に良い数字が出ない可能性は 1e-8 .

そこで、解決策を紹介します。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
)

func RandStringBytesMask(n int) string {
    b := make([]byte, n)
    for i := 0; i < n; {
        if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i++
        }
    }
    return string(b)
}

5. マスキングの改善

が返す 63 個のランダムビットのうち、下位 6 ビットのみを使用するものでした。 rand.Int63() . ランダムビットの取得は、このアルゴリズムの最も遅い部分であるため、これは無駄なことです。

52個の文字があるとすると、6ビットで1つの文字のインデックスを符号化することになります。つまり、63ビットのランダムビットで 63/6 = 10 異なる文字インデックスを持つその10個を全部使ってみよう。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

func RandStringBytesMaskImpr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdxMax letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

6. ソース

は マスキングを改善 はかなり良いもので、あまり改善できるところはありません。改善することは可能ですが、複雑にするほどの価値はありません。

では、他に改善すべき点を探してみましょう。 乱数の発生源。

があります。 crypto/rand を提供するパッケージです。 Read(b []byte) 関数を使えば、1回の呼び出しで必要なだけのバイトを取得することができます。これは、パフォーマンスの面では crypto/rand は暗号的に安全な擬似乱数生成器を実装しているため、より低速になります。

そこで math/rand パッケージを使用します。その rand.Rand を使用します。 rand.Source をランダムビットのソースとして使用します。 rand.Source を指定するインターフェースです。 Int63() int64 メソッドです。まさに、私たちが必要とし、最新のソリューションで使用した唯一のものです。

だから rand.Rand (明示的またはグローバルな、共有された1つの rand パッケージ)を使用すると rand.Source で十分なのです。

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 < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

また、この最後の解決策では、グローバルな Rand の math/rand パッケージは使用されないので（そして私たちの rand.Source は適切に初期化/シードされます)。

もう一つ、ここで注意しなければならないのは math/rand という記述があります。

デフォルトのSourceは、複数のゴルーチンによる同時使用にも安全です。

ということは、デフォルトのソースは Source で取得できる可能性があること rand.NewSource() なぜなら、デフォルトのソースは同時アクセス/使用に対する安全性を提供しなければならないのに対し rand.NewSource() はこれを提供しない（そのため Source が返す方が高速になる可能性が高いです。）

7. 活用法 `strings.Builder`

これまでのすべての解決策は string そのコンテンツは、まずスライスで構築されます ( []rune で 創世記 であり、かつ []byte に変換され、それ以降のソリューションでは string . この最終的な変換では、スライスの内容をコピーする必要があります。 string 値は不変であり、もし変換がコピーを作成しないなら、文字列の内容が元のスライスを介して変更されないことが保証されない可能性があります。詳しくは utf8文字列を[]byteに変換する方法は？そして golangです。[]byte(string) vs []byte(*string) .

Go 1.10導入 strings.Builder . strings.Builder の内容を構築するために使用できる新しい型です。 string と同様に bytes.Buffer . 内部的には []byte を使ってコンテンツを構築し、それが終わったら最終的に string の値は、その Builder.String() メソッドを使用します。しかし、このメソッドが優れているのは、上で説明したようなコピーを実行せずに、この処理を行うことです。これは、文字列の内容を構築するために使用されるバイトスライスが公開されていないため、誰も意図せず、または悪意を持ってそれを変更して、生成された "immutable"文字列を変更できないことが保証されているため、あえてそうしているのです。

そこで、次のアイデアとして、ランダムな文字列をスライスで構築するのではなく strings.Builder そうすれば、コピーを作成することなく、結果を取得し、返すことができます。これはスピードの面でも、メモリの使用量や割り当ての面でも、間違いなく役に立ちます。

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 < len(letterBytes) {
            sb.WriteByte(letterBytes[idx])
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return sb.String()
}

を作成した後、新しい strings.Buidler を呼び出すと、その Builder.Grow() メソッドで、十分な大きさの内部スライスを確保するようにします (ランダムな文字を追加する際に再割り当てされないようにするため)。

8. "ミミシング" `strings.Builder` パッケージ付き `unsafe`

strings.Builder は、文字列を内部の []byte のように、自分たちでやったのと同じです。ですから基本的には strings.Builder には多少のオーバーヘッドがありますが、唯一、私たちが切り替えたのは strings.Builder は、スライスの最終的なコピーを回避するためです。

strings.Builder は、最終的なコピーを避けるために、パッケージ unsafe :

// String returns the accumulated string.
func (b *Builder) String() string {
    return *(*string)(unsafe.Pointer(&b.buf))
}

このようなことも、自分たちでできるということです。つまり、ここでのアイデアは、ランダムな文字列の構築に戻るために []byte しかし、それが終わったら、それを string を返すのではなく、安全でない変換を行います。 string で、そのバイトスライスを文字列データとして指し示します。

このようにすることができます。

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 < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return *(*string)(unsafe.Pointer(&b))
}

(9.使用方法 `rand.Read()` )

Go 1.7を追加しました。 a rand.Read() 関数と Rand.Read() メソッドを使用します。これらを使って、必要なだけのバイトを一度に読み込むことで、より良いパフォーマンスを実現したくなるはずです。

この場合、1つだけ小さな問題があります。出力する文字の数と同じだけ必要です。文字インデックスは8ビット（1バイト）未満しか使用しないので、これは高く見積もっていると思われます。しかし、この時点ですでに悪化しており（ランダムビットの取得が難しいため）、必要以上のものを得ていることになります。

また、すべての文字インデックスの均等な分布を維持するために、使用できないゴミのようなランダムデータがあるかもしれないので、いくつかのデータをスキップすることになり、すべてのバイトスライスを通過したときに不足することになることに注意してください。そのため、さらに多くのランダムバイトを取得する必要があります（quot;recursively"）。そして今、私たちはさらに、quot;への単一の呼び出しを失っています。 rand package"の利点は...。

から取得したランダムデータの利用を、多少なりとも最適化することができました。 math.Rand() . 何バイト（何ビット）必要かを見積もることができる。1文字に必要なのは letterIdxBits ビットが必要であり n 文字が必要なので n * letterIdxBits / 8.0 バイトの四捨五入です。ランダムインデックスが使用できない確率を計算できるので（上記参照）、十分である可能性が高いものをさらに要求することができます（そうでないことが判明した場合は、このプロセスを繰り返すことになります）。例えば、バイトスライスをビットストリームとして処理することができます。 github.com/icza/bitio (開示：私が作者です)。

しかし、Benchmarkのコードでは、まだ勝てていないことがわかります。なぜなのでしょうか？

最後の質問の答えは、以下の通りです。 rand.Read() はループを使用しており Source.Int63() 渡されたスライスを埋めるまでまさに RandStringBytesMaskImprSrc() のソリューションが行います。なくを追加することなく、中間バッファを使用することができます。そのため RandStringBytesMaskImprSrc() が王座に残っています。そうです。 RandStringBytesMaskImprSrc() は、非同期の rand.Source とは異なり rand.Read() . しかし、その理由はまだ適用されます。 Rand.Read() の代わりに rand.Read() (前者も非同期化される)。

II. ベンチマーク

それでは、いよいよ各ソリューションのベンチマークを行います。

正念場です。

BenchmarkRunes-4                     2000000    723 ns/op   96 B/op   2 allocs/op
BenchmarkBytes-4                     3000000    550 ns/op   32 B/op   2 allocs/op
BenchmarkBytesRmndr-4                3000000    438 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMask-4                 3000000    534 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImpr-4            10000000    176 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImprSrc-4         10000000    139 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImprSrcSB-4       10000000    134 ns/op   16 B/op   1 allocs/op
BenchmarkBytesMaskImprSrcUnsafe-4   10000000    115 ns/op   16 B/op   1 allocs/op

ルーンからバイトに切り替えただけで、すぐに 24% パフォーマンスが向上し、必要なメモリ容量が 3分の1 .

を取り除くこと rand.Intn() を使用し rand.Int63() の代わりに、別の 20% を高めることができます。

マスキング（と大きなインデックスの場合の繰り返し）が少し遅くなる（繰り返しの呼び出しのため）。 -22% ...

しかし、63個のランダムビットのすべて（またはほとんど）を使用すると、1つの rand.Int63() の呼び出し): それは大きな時間をスピードアップします。 3回 .

で解決すると、（デフォルトでない、新しい） rand.Source ではなく rand.Rand を使用すると、再び 21%.

を活用すると strings.Builder を使用すると、小さな 3.5% で スピード を達成しました。 50% メモリ使用量とメモリ割り当てを削減! それはいいことだ!

最後に、あえてパッケージ unsafe の代わりに strings.Builder を使用すると、またしても素敵な 14% .

最終解と初期解を比較する。 RandStringBytesMaskImprSrcUnsafe() は 6.3倍高速化 よりも RandStringRunes() を使用しています。 六分の一 メモリと アロケーションが半分に . ミッション達成。