Go で、数字を含まない、文字のみ (大文字または小文字) のランダムな文字列を作成したいです。これを行う最も速く簡単な方法は何ですか?
ベストアンサー1
ポールの解決策シンプルで一般的なソリューションを提供します。
質問では「最も速くて簡単な方法」を尋ねています。最速の部分についても説明しましょう。反復的な方法で、最終的な最速のコードに到達します。各反復のベンチマークは、回答の最後にあります。
すべてのソリューションとベンチマークコードは、遊び場に行くXX_test.goプレイグラウンドのコードはテストファイルであり、実行ファイルではありません。 という名前のファイルに保存して、
go test -bench . -benchmem
序文:
ランダムな文字列だけが必要な場合、最速のソリューションは頼りになるソリューションではありません。その場合、Paul のソリューションは最適です。ただし、パフォーマンスが重要な場合は別です。最初の 2 つのステップ ( BytesとRemainder ) は妥協案として許容できるかもしれませんが、パフォーマンスは 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 エンコーディング (Go が文字列を保存する方法) では英語のアルファベットの文字がバイトに 1 対 1 でマッピングされるため、バイトのみで作業できます。
したがって、次の代わりに:
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
以下を使用できます:
var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
あるいは、さらに良いのは:
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
これはすでに大きな改善です。これをconst（string定数はありますが）スライス定数はありません）。追加の利点として、式は!len(letters)にもなります(が文字列定数の場合、const式はlen(s)定数になります)。s
コストはいくらですか? まったくかかりません。strings はインデックス化でき、そのバイトをインデックス化します。完璧です。まさに私たちが求めているものです。
次の目的地は次のようになります。
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)
}
これは機能し、大幅に高速化されますが、すべての文字の確率がまったく同じではないという欠点があります ( がすべての 63 ビットの数字を等しい確率で生成すると仮定)。文字の数は よりもはるかに少ないrand.Int63()ため、歪みは極めて小さく、実際にはこれでまったく問題ありません。521<<63 - 1
これをもっと簡単に理解するために、 の範囲の乱数が必要だとします。3 ビットのランダム ビットを使用すると、範囲 よりも 2 倍の確率で0..5数値が生成されます。5 ビットのランダム ビットを使用すると、範囲内の数値はの確率で発生し、範囲内の数値は の確率で発生するため、目的に近づきます。ビット数を増やすと、この影響は小さくなり、63 ビットに達すると無視できるようになります。0..12..50..16/322..55/32
4. マスキング
前のソリューションを基にして、文字数を表すために必要な数の乱数の最低ビットのみを使用して、文字の均等な配分を維持することができます。たとえば、文字が 52 個ある場合、それを表すには 6 ビットが必要です。52 = 110100bしたがって、 によって返される数値の最低 6 ビットのみを使用しますrand.Int63()。また、文字の均等な配分を維持するために、数値が の範囲内にある場合にのみ「受け入れ」ます0..len(letterBytes)-1。最低ビットが大きい場合は、その数値を破棄して新しい乱数を照会します。
最下位ビットが より大きいか に等しい可能性は、一般に（平均して）len(letterBytes)より低いことに注意してください。つまり、たとえそうなったとしても、この「まれな」ケースを繰り返すと、適切な数字が見つからない可能性が低くなります。繰り返しの後、適切なインデックスが得られない可能性は よりはるかに低く、これは上限の推定値にすぎません。52 文字の場合、最下位 6 ビットが適切でない可能性は のみです。つまり、たとえば 10 回の繰り返し後に適切な数字が得られない可能性は です。0.50.25npow(0.5, n)(64-52)/64 = 0.191e-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 ビットで文字インデックスをコード化します。つまり、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.Randrand.Sourceランダム ビットのソースとして。メソッドrand.Sourceを指定するインターフェイスですInt63() int64。これはまさに、最新のソリューションで必要となり、使用された唯一のものです。
rand.Randしたがって、 （明示的なものでも、パッケージのグローバルで共有されたものでも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ここでもう1つ注意すべき点:状態のパッケージドキュメント:
デフォルトの Source は、複数の goroutine による同時使用でも安全です。
したがって、デフォルトのソースは、Sourceによって取得されるよりも低速になります。これrand.NewSource()は、デフォルトのソースは同時アクセス/使用時の安全性を提供する必要があるのに対し、 はrand.NewSource()これを提供していないためです (したがって、Sourceによって返される の方が高速になる可能性が高くなります)。
7. 活用strings.Builder
これまでのソリューションはすべて を返します。stringその内容は最初にスライス（Genesisおよびそれ以降のソリューション）[]runeで構築され、次に に変換されます。この最終的な変換では、スライスの内容のコピーを作成する必要があります。値は不変であり、変換でコピーが作成されない場合、文字列の内容が元のスライスによって変更されないことが保証されないためです。詳細については、を参照してください。[]bytestringstringutf8文字列を[]byteに変換するにはどうすればいいですか?そしてgolang: []byte(string) と []byte(*string)。
Go 1.10 が導入されましたstrings.Builder。 strings.Builderstringは、次のようなコンテンツを構築するために使用できる新しいタイプです。bytes.Buffer内部的にはを使用して[]byteコンテンツを構築し、完了したら、stringそのを使用して最終的な値を取得できます。Builder.String()方法。しかし、この方法の素晴らしい点は、上で説明したコピーを実行せずにこれを実行することです。文字列の内容を構築するために使用されるバイト スライスが公開されていないため、誰も意図せずまたは悪意を持ってそれを変更して、生成された「不変」な文字列を変更できないことが保証されるため、あえてこれを実行します。
そこで次のアイデアは、スライス内でランダムな文字列を構築せず、 の助けを借りて、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()メソッドは、十分な大きさの内部スライスを割り当てるようにします (ランダムな文字を追加するときに再割り当てを回避するため)。
strings.Builder8.パッケージによる「模倣」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 が追加されました1つのrand.Read()機能とRand.Read()メソッド。パフォーマンスを向上させるために、必要なバイト数を 1 ステップで読み取るためにこれらのメソッドを使用することをお勧めします。
これには小さな「問題」が 1 つあります。必要なバイト数はどれくらいでしょうか。出力文字の数と同じ数と言えます。文字インデックスは 8 ビット (1 バイト) 未満を使用するため、これは上限の見積もりであると考えられます。しかし、この時点ですでに状況は悪化しており (ランダム ビットを取得するのが「難しい部分」であるため)、必要以上のバイトを取得しています。
また、すべての文字インデックスの均等な配分を維持するために、使用できない「ゴミ」ランダム データが存在する可能性があり、その結果、一部のデータがスキップされ、すべてのバイト スライスを調べるときに不足することになります。さらに、「再帰的に」ランダム バイトを取得する必要があります。これで、「randパッケージへの単一の呼び出し」の利点さえ失われます...
から取得したランダム データの使用を「ある程度」最適化できますmath.Rand()。必要なバイト数 (ビット数) を見積もることができます。1 文字にはletterIdxBitsビット数が必要で、n文字が必要なので、n * letterIdxBits / 8.0バイトを切り上げる必要があります。ランダム インデックスが使用できない確率を計算できます (上記を参照)。そのため、「より可能性が高い」十分な数を要求できます (十分でないことが判明した場合は、このプロセスを繰り返します)。たとえば、バイト スライスを「ビット ストリーム」として処理できます。これには、優れたサードパーティ ライブラリがあります。github.com/icza/bitio(開示：私は著者です)。
しかし、ベンチマーク コードでは、まだ勝てていないことが示されています。なぜでしょうか?
最後の質問の答えは、 がrand.Read()ループを使用し、Source.Int63()渡されたスライスがいっぱいになるまで を呼び出し続けるからです。中間バッファや追加の複雑さなしでRandStringBytesMaskImprSrc()、ソリューションが行うこととまったく同じです。これがが王座に留まっている理由です。はい、はとは異なり、非同期を使用します。しかし、論理は依然として適用され、の代わりにを使用すると証明されます(前者も非同期です)。RandStringBytesMaskImprSrc()RandStringBytesMaskImprSrc()rand.Sourcerand.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()呼び出しから 10 個のインデックス) のすべて (またはほとんど) を使用すると、速度が大幅に向上します ( 3 倍)。
rand.Sourceの代わりに(デフォルトではない新しい) で決済するとrand.Rand、再び21% の利益が得られます。
を利用すると、速度がstrings.Builderわずか3.5%向上しますが、メモリ使用量と割り当ても50%削減されます。すばらしいですね。
unsafe最後に、の代わりにパッケージを使用すると、再び14%strings.Builderという素晴らしい が得られます。
最終ソリューションと初期ソリューションを比較すると、RandStringBytesMaskImprSrcUnsafe()はよりも6.3 倍高速RandStringRunes()で、メモリ使用量は6 分の 1 になり、割り当て数は半分になります。ミッションは完了です。