Go言語でランダムな文字列を生成する方法の比較

こちらの記事で議論されていた内容を実際にやってみました。

1. 一番標準的なやり方

[a-zA-Z]のランダムなn文字の文字列を生成します。
まず元となるa-zA-Zのruneのスライスを用意します。rand.Intn(k)は0以上k未満のランダムな整数を返すので、kにスライスの長さを入れてスライスのどれかの文字をランダムに返すようにします。その文字を結果のスライスに追加していくようにします。
ちなみにinit()では乱数の種に現在時刻のナノ秒を設定しています。

import (
	"math/rand"
	"time"
)

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

var rs1Letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandString1(n int) string {
	b := make([]rune, n)
	for i := range b {
		b[i] = rs1Letters[rand.Intn(len(rs1Letters))]
	}
	return string(b)
}

2. constを使ってみる

runeのスライスで用意していた部分をconstの文字列で用意することで計算量を減らします。constに対するlen()もconstになりますので計算が発生しなくなります。

const rs2Letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

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

3. rand.Int63()を使う

rand.Intn()は内部的にrand.Int31n()、rand.Int31()、そして最終的にrand.Int63()を呼び出すので、rand.Int63()を直接使ったほうが速いはずです。
（※私の環境では速くはなりませんでした。最後のベンチマークを参照）
rand.Int63()は63ビットの長さのint64の整数を返します。元の文字列の長さでランダムな数値で割った余りを使えば、文字列からランダムに文字をピックアップできるはずです。

const rs3Letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

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

4. 3のやり方の歪みを補正する

実は3で作られた文字列にはわずかに歪みがあります。
例えば0～5しか乱数がない世界を考えてみましょう。この時に0～3の乱数を得たいと考えて0～5の乱数を4で割った時に、余り0が出るのは0,4、余り3が出るのは3の時だけで確率に偏りが出ています。これを防ぐには、4以上の数が出たらその乱数を捨てて、新しい乱数を再取得することです。
元の文字列は52文字なので、63ビットの乱数のうち6ビットあれば十分です。6ビット分をマスクして、さらに結果のうち52以上のものは捨てるようにします。

const (
	rs4Letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	rs4LetterIdxBits = 6
	rs4LetterIdxMask = 1<<rs4LetterIdxBits - 1
)

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

5. 4のやり方をさらに向上させる

4のやり方では63ビットのうち6ビットしか使っておらず、しかも取得した整数が52を超えている場合は捨ててしまっています。63ビットの乱数を6ビットずつに分割してすべて使い切るようにし、乱数取得回数を減らせば大幅に早くなるはずです。

const (
	rs5Letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	rs5LetterIdxBits = 6
	rs5LetterIdxMask = 1<<rs5LetterIdxBits - 1
	rs5LetterIdxMax = 63 / rs5LetterIdxBits
)

func RandString5(n int) string {
	b := make([]byte, n)
	cache, remain := rand.Int63(), rs5LetterIdxMax
	for i := n-1; i >= 0; {
		if remain == 0 {
			cache, remain = rand.Int63(), rs5LetterIdxMax
		}
		idx := int(cache & rs5LetterIdxMask)
		if idx < len(rs5Letters) {
			b[i] = rs5Letters[idx]
			i--
		}
		cache >>= rs5LetterIdxBits
		remain--
	}
	return string(b)
}

6. グローバルなrandを使うのをやめる

乱数発生源としてグローバルなrandに種を設定して使っていますが、これはrand.Sourceで十分です。init()で乱数の種を設定している部分をvarの宣言に含めてしまいます。

var randSrc = rand.NewSource(time.Now().UnixNano())

const (
	rs6Letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	rs6LetterIdxBits = 6
	rs6LetterIdxMask = 1<<rs6LetterIdxBits - 1
	rs6LetterIdxMax = 63 / rs6LetterIdxBits
)

func RandString6(n int) string {
	b := make([]byte, n)
	cache, remain := randSrc.Int63(), rs6LetterIdxMax
	for i := n-1; i >= 0; {
		if remain == 0 {
			cache, remain = randSrc.Int63(), rs6LetterIdxMax
		}
		idx := int(cache & rs6LetterIdxMask)
		if idx < len(rs6Letters) {
			b[i] = rs6Letters[idx]
			i--
		}
		cache >>= rs6LetterIdxBits
		remain--
	}
	return string(b)
}

7. ベンチマーク

上記の1～6の内容をベンチマークで比較してみましょう。16文字のランダムな文字列を生成した結果の比較です。(Windows7-32bit + Go1.7)

BenchmarkRandString1-4           1000000              1696 ns/op
BenchmarkRandString2-4           1000000              1378 ns/op
BenchmarkRandString3-4           1000000              1834 ns/op
BenchmarkRandString4-4           1000000              1322 ns/op
BenchmarkRandString5-4           3000000               456 ns/op
BenchmarkRandString6-4           5000000               382 ns/op

環境が違うせいか元の記事とは少し傾向が違う結果になりました。ちなみに元の記事の結果は以下のとおりです。元の記事のコードはGo Playgroundにあります。

BenchmarkRunes                   1000000              1703 ns/op
BenchmarkBytes                   1000000              1328 ns/op
BenchmarkBytesRmndr              1000000              1012 ns/op
BenchmarkBytesMask               1000000              1214 ns/op
BenchmarkBytesMaskImpr           5000000               395 ns/op
BenchmarkBytesMaskImprSrc        5000000               303 ns/op