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