Go

Go言語でランダムな文字列を作ってみる

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

結果用のバッファと、乱数用のバッファで、ふたつ確保しているけれど、1つでいいのではないか。乱数をバッファに読み込んで、文字に置き換えていく方式。

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 が参考になります。