Shogo's Blog

たぶんプログラミングとかについて書いていくブログ

String::RandomのGo移植を書いてみた

golangkyotoでString::RandomのGo移植についての発表があったと聞き、 これに対抗して以前途中まで書いていたString::RandomのGo移植をちょっといじって公開しました。

背景

ナイーブな実装の問題点

実はgolangkyoto以前にもGoの正規表現エンジンを使ってランダムな文字列を生成する試みはあって、 たしかにこれは面白そうだと記事を読んでいました。

しかし、gocha同様、この実装では文字列の長さが幾何分布に従うため、短い文字が多めにでてしまいます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
% 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 オプションについては後述)

1
2
3
4
5
6
7
8
9
10
11
$ 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}のような正規表現でも、それぞれのパターンがおおよそ同じ数だけ生成されます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ 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]abにマッチするので2パターン」と解釈していましたが、 「[ab]のような1文字にマッチするパターンは全部1パターン」と緩い解釈にするようにしました。 -dオプションはこの挙動を制御するためのオプションです。

デフォルトの挙動は「1文字にマッチするパターンは全部1パターン」です。 さきほどと同じ[ab]{1,3}で、-dオプションを外しデフォルトの設定で文字列生成すると以下のようになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ 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

abが多めに出ているような気がしますが、 文字列長別に集計するとおおよそ同じ回数だけ出現していることが確認できます。

1
2
3
4
$ 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}で電話番号っぽい文字列を生成するベンチです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
$ 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の中でやってほしい!というのが僕の意見です。

1
2
3
4
// main.goの中でやってほしい!
func init() {
    rand.Seed(time.Now().UnixNano())
}

ベストなのは ライブラリではグローバルなmath/rand関数を使わない! ことです。 rerandでは以下のようにrand.Newを使って、グローバルな関数は使っていません。

1
r = rand.New(rand.NewSource(time.Now().UnixNano()))

goroutine-unsafeになってしまうので、同期処理を自前で書く必要があるのが難点です。 その代わり、ロックの粒度が細かく調整できるので、並列処理の効率は上がるはずです(たぶん)。

また、テストの際にSeedを固定できるので便利です。

1
r = rand.New(rand.NewSource(1))

gocha互換オプション

-prob 0.5でGochaと同じ挙動になるはずです。 a*のような無限長の正規表現も扱えます。 数値をいじることで文字列の長さの分布を調整可能です。

まとめ

  • Go版String::Randomを作った
  • ライブラリではグローバルなmath/rand関数をなるべく使わないでほしい!

参考

Comments