golangkyotoでString::RandomのGo移植についての発表があったと聞き、 これに対抗して以前途中まで書いていたString::RandomのGo移植をちょっといじって公開しました。
背景
ナイーブな実装の問題点
実はgolangkyoto以前にもGoの正規表現エンジンを使ってランダムな文字列を生成する試みはあって、 たしかにこれは面白そうだと記事を読んでいました。
しかし、gocha同様、この実装では文字列の長さが幾何分布に従うため、短い文字が多めにでてしまいます。
% gocha -n 100000 'a*' | sort | uniq -c
50054
24894 a
12633 aa
6278 aaa
2994 aaaa
1517 aaaaa
809 aaaaaa
400 aaaaaaa
206 aaaaaaaa
109 aaaaaaaaa
54 aaaaaaaaaa
22 aaaaaaaaaaa
15 aaaaaaaaaaaa
7 aaaaaaaaaaaaa
4 aaaaaaaaaaaaaa
3 aaaaaaaaaaaaaaa
1 aaaaaaaaaaaaaaaa
正規表現のパターンを数え上げとその問題点
この問題を解決するために 「この先何パターンあるかを調べておけば、正規表現が表す文字列の集合からランダムに文字列を取り出せるのでは？」 と考え、golangkyoto以前からちょこちょこ実装を進め、不完全ながらも一応動作するところまでは書いていたのです。 有向グラフの経路数えあげ問題なので、メモ化再帰を使って頑張れば解けます。 少々面倒ですが、おねえさんの問題と比べれば簡単です。
パターンを数え上げる都合上、組み合わせが無限にある a* ような正規表現は扱えません。
a{1,10} のように明示的に範囲を指定する必要があります。
たとえば a{1,10} は10パターン組み合わせがあるので、20万個ランダムに生成すると、それぞれのパターンがおおよそ2万個ずつ生成されます。
(-d オプションについては後述)
$ rerand -d -n 200000 'a{1,10}' | sort | uniq -c
20153 a
19863 aa
19899 aaa
19908 aaaa
19975 aaaaa
20000 aaaaaa
20081 aaaaaaa
20021 aaaaaaaa
20072 aaaaaaaaa
20028 aaaaaaaaaa
[ab]{1,3}のような正規表現でも、それぞれのパターンがおおよそ同じ数だけ生成されます。
$ rerand -d -n 200000 '[ab]{1,3}' | sort | uniq -c
14299 a
14249 aa
14215 aaa
14257 aab
14192 ab
14340 aba
14317 abb
14209 b
14213 ba
14332 baa
14228 bab
14355 bb
14634 bba
14160 bbb
これはこれで意図した挙動なのですが、 1文字のパターン数に比べて、3文字のパターン数が非常に多いため、相対的に短い文字列が出現しにくくなってしまいます。 「これは本当にユーザーが望んだものなのだろうか・・・？」と疑問に思ってしまい、 うまい解決策が思いつかないままずっと放置していました。
文字グループの同一視
ここまで実装では正規表現の定義に厳密に従い「[ab]はaとbにマッチするので2パターン」と解釈していましたが、
「[ab]のような1文字にマッチするパターンは全部1パターン」と緩い解釈にするようにしました。
-dオプションはこの挙動を制御するためのオプションです。
デフォルトの挙動は「1文字にマッチするパターンは全部1パターン」です。
さきほどと同じ[ab]{1,3}で、-dオプションを外しデフォルトの設定で文字列生成すると以下のようになります。
$ rerand -n 200000 '[ab]{1,3}' | sort | uniq -c
33463 a
16432 aa
8392 aaa
8206 aab
16806 ab
8334 aba
8403 abb
33242 b
16549 ba
8393 baa
8372 bab
16644 bb
8376 bba
8388 bbb
aやbが多めに出ているような気がしますが、
文字列長別に集計するとおおよそ同じ回数だけ出現していることが確認できます。
$ rerand -n 200000 '[ab]{1,3}' | perl -nE 'chomp; say length' | sort -n | uniq -c
66769 1
67036 2
66195 3
これで少しはユーザーフレンドリーになったはず(？)
ベンチマーク
ベンチマークの結果も貼っておきます。
coffeescriptは コーフィースクリップトの発音を生成するベンチマーク、
telephoneは\d{2,3}-\d{3,4}-\d{3,4}で電話番号っぽい文字列を生成するベンチです。
$ go test -run none -bench . -benchmem ./...
BenchmarkGenerator/coffeescript-4 1000000 1737 ns/op 81 B/op 2 allocs/op
BenchmarkGenerator/[あ-お]{10}-4 2000000 845 ns/op 80 B/op 2 allocs/op
BenchmarkGenerator/[[:alpha:]]-4 5000000 274 ns/op 36 B/op 2 allocs/op
BenchmarkGenerator/\S-4 5000000 292 ns/op 40 B/op 2 allocs/op
BenchmarkGenerator/\S{10}-4 1000000 1568 ns/op 80 B/op 2 allocs/op
BenchmarkGenerator/\pN-4 5000000 304 ns/op 39 B/op 2 allocs/op
BenchmarkGenerator/\p{Greek}-4 5000000 299 ns/op 39 B/op 2 allocs/op
BenchmarkGenerator/telephone-4 2000000 886 ns/op 48 B/op 2 allocs/op
BenchmarkRuneGenerator/[a]-4 300000000 4.24 ns/op 0 B/op 0 allocs/op
BenchmarkRuneGenerator/[a-z]-4 30000000 42.7 ns/op 0 B/op 0 allocs/op
BenchmarkRuneGenerator/[a-zA-Z0-9]-4 10000000 118 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/shogo82148/go-rerand 20.013s
? github.com/shogo82148/go-rerand/cmd/rerand [no test files]
BenchmarkGocha/coffeescript-4 300000 3967 ns/op 1090 B/op 34 allocs/op
BenchmarkGocha/[あ-お]{10}-4 1000000 1951 ns/op 328 B/op 15 allocs/op
BenchmarkGocha/[[:alpha:]]-4 5000000 323 ns/op 64 B/op 4 allocs/op
BenchmarkGocha/\S-4 5000000 394 ns/op 128 B/op 5 allocs/op
BenchmarkGocha/\S{10}-4 500000 3353 ns/op 1288 B/op 35 allocs/op
BenchmarkGocha/\pN-4 1000000 1988 ns/op 4096 B/op 10 allocs/op
BenchmarkGocha/\p{Greek}-4 1000000 1122 ns/op 2048 B/op 9 allocs/op
BenchmarkGocha/telephone-4 1000000 1998 ns/op 288 B/op 14 allocs/op
PASS
ok github.com/shogo82148/go-rerand/gocha_test 14.405s
BenchmarkStrRand/coffeescript-4 1000000 1828 ns/op 262 B/op 11 allocs/op
BenchmarkStrRand/[あ-お]{10}-4 1000000 1189 ns/op 208 B/op 9 allocs/op
BenchmarkStrRand/\S-4 20000000 72.9 ns/op 0 B/op 0 allocs/op
BenchmarkStrRand/\S{10}-4 1000000 1097 ns/op 64 B/op 9 allocs/op
BenchmarkStrRand/telephone-4 1000000 1409 ns/op 58 B/op 10 allocs/op
PASS
ok github.com/shogo82148/go-rerand/strrand_test 7.136s
テストケースにもよりますが、Songmuさんのstrrandと同等かちょっと速い程度の性能です(シンプルな正規表現ではstrrandが速いこともある)。 Twitterには「Gocha速い！」みたいなことが流れてましたが、僕の手元での検証ではstrrandの方が高速でした。 どうもベンチマークの使い方間違っていたっぽいですね・・・。
ちなみにこのベンチマークには正規表現をパースする処理は入っていません。 (どう考えてもstrrandに負けるのは目に見えている) たいていのケースで初期化一回なので気にしない気にしない。
グローバルなmath/rand関数の扱い
go-rerandを作る際、他の実装も参考にしたのですが、 Seedの初期化のタイミングがまちまちで、少し気になりました。
- fuzzingo:
rand.Intnを使う直前(！) - strrand: init関数内
- gocha: Newの中
Seedの初期化は本来一回だけでいいので、「rand.Intnを使う直前」や「Newの中」で行うのは無駄です。
init関数内でやる方法がベターですが、math/randを使うライブラリを複数importしている場合、
結局何度もSeedの初期化が行われてしまいます。
ライブラリ利用者の手間は増えますが、ライブラリの中ではなくmain.goの中でやってほしい！というのが僕の意見です。
// main.goの中でやってほしい！
func init() {
rand.Seed(time.Now().UnixNano())
}
ベストなのは ライブラリではグローバルなmath/rand関数を使わない！ ことです。
rerandでは以下のようにrand.Newを使って、グローバルな関数は使っていません。
r = rand.New(rand.NewSource(time.Now().UnixNano()))
goroutine-unsafeになってしまうので、同期処理を自前で書く必要があるのが難点です。 その代わり、ロックの粒度が細かく調整できるので、並列処理の効率は上がるはずです(たぶん)。
また、テストの際にSeedを固定できるので便利です。
r = rand.New(rand.NewSource(1))
gocha互換オプション
-prob 0.5でGochaと同じ挙動になるはずです。
a*のような無限長の正規表現も扱えます。
数値をいじることで文字列の長さの分布を調整可能です。
まとめ
- Go版String::Randomを作った
- ライブラリではグローバルなmath/rand関数をなるべく使わないでほしい！