Go言語で、ランダムな文字列を生成する方法について考えてみます。
この記事では math/rand ではなく crypto/rand を使います。
※記事中で最終的に実装したものは https://github.com/najeira/randstr パッケージ化しましたので、ただ使いたい場合はそちらで。
Phase 1
まず単純に考えて、文字種の範囲内で乱数を生成して、文字列からピックアップしていきます。
crypto/rand だと [0, max) の乱数を生成してくれる Int 関数に max として big.Int を渡します。
package randstr
import (
"crypto/rand"
"math/big"
)
const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
func Phase1(n int) string {
buf := make([]byte, n)
max := new(big.Int)
max.SetInt64(int64(len(letterBytes)))
for i := range buf {
r, err := rand.Int(rand.Reader, max)
if err != nil {
panic(err)
}
buf[i] = letterBytes[r.Int64()]
}
return string(buf)
}
func BenchmarkPhase1(b *testing.B) {
for i := 0; i < b.N; i++ {
Phase1(100)
}
}
BenchmarkPhase1-4 50000 29519 ns/op 8372 B/op 303 allocs/op
※Phase 2 以降もベンチマークのコードは同等
Int 関数内で new(big.Int) が実行されるので、パフォーマンスはあまりよくありません。
new(big.Int) …… ISUCON 7 で見たな……
Phase 2
文字はアルファベット大小と数字で62文字あります。62文字ということは6ビットの範囲内です。なので、1バイト(8ビット)の乱数を取得して、6ビット分だけ使えばよさそうです。
1バイトの乱数を取得し、6ビットでマスクします。この最大値が63で、62と63が文字種の数を超えるので、その場合は無視してやり直し。61以下なら文字をピックアップします。
package randstr
import (
"crypto/rand"
"math/big"
)
const (
letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
letterIdxMask = 0x3F // 63 0b111111
)
func Phase2(n int) string {
src := make([]byte, 1)
buf := make([]byte, n)
for i := 0; i < n; {
if _, err := rand.Read(src); err != nil {
panic(err)
}
idx := int(src[0] & letterIdxMask)
if idx < len(letterBytes) {
buf[i] = letterBytes[idx]
i++
}
}
return string(buf)
}
BenchmarkPhase2-4 100000 19922 ns/op 225 B/op 3 allocs/op
だいぶ速くなりました。
Phase 3
1バイトずつ乱数を読まずに、いっきに数バイト読み込めばいいのではないか。
package randstr
import (
"crypto/rand"
"math/big"
)
const (
letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
letterIdxMask = 0x3F // 63 0b111111
)
func Phase3(n int) string {
src := make([]byte, n)
buf := make([]byte, n)
for i, j := 0, 0; i < n; j++ {
pos := j % n
if pos == 0 {
if _, err := rand.Read(src); err != nil {
panic(err)
}
}
idx := int(src[pos] & letterIdxMask)
if idx < len(letterBytes) {
buf[i] = letterBytes[idx]
i++
}
}
return string(buf)
}
BenchmarkPhase3-4 100000 18506 ns/op 336 B/op 3 allocs/op
さほど速くならず、メモリ消費がアップ。
ただ、生成する文字列の長さが短い（例えば10）のときは、Phase3はPhase2より速いです。10文字でのベンチマーク:
BenchmarkPhase2-4 1000000 1625 ns/op 32 B/op 3 allocs/op
BenchmarkPhase3-4 1000000 1222 ns/op 48 B/op 3 allocs/op
Phase 4
結果用のバッファと、乱数用のバッファで、ふたつ確保しているけれど、１つでいいのではないか。乱数をバッファに読み込んで、文字に置き換えていく方式。
package randstr
import (
"crypto/rand"
"math/big"
)
const (
letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
letterIdxMask = 0x3F // 63 0b111111
)
func Phase4(n int) string {
buf := make([]byte, n)
if _, err := rand.Read(buf); err != nil {
panic(err)
}
for i := 0; i < n; {
idx := int(buf[i] & letterIdxMask)
if idx < len(letterBytes) {
buf[i] = letterBytes[idx]
i++
} else {
if _, err := cryptorand.Read(buf[i:i+1]); err != nil {
panic(err)
}
}
}
return string(buf)
}
BenchmarkPhase4-4 200000 9144 ns/op 224 B/op 2 allocs/op
速くなった。
まとめ:
BenchmarkPhase1-4 50000 29519 ns/op 8372 B/op 303 allocs/op
BenchmarkPhase2-4 100000 19922 ns/op 225 B/op 3 allocs/op
BenchmarkPhase3-4 100000 18506 ns/op 336 B/op 3 allocs/op
BenchmarkPhase4-4 200000 9144 ns/op 224 B/op 2 allocs/op
なお、pprof で Phase4 を調べてみると crypto.Read から呼ばれる syscall.Syscall が支配的。
どなたか、もうちょっと速くできたりしますでしょうか？
また、乱数的にまずい処理があれば教えてください！
License: MIT
なお math/rand の場合では https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-golang が参考になります。