文字種チェック用の読みやすくて速い正規表現
前回の日記で「クライアントに的確なエラーメッセージを返すため、文字種のチェックと文字数のチェックは分けて行うべきかもしれない」と書いた。
このうち、文字数のチェックは簡単である。文字数をカウントし、許容文字数を超えていないかどうか調べるだけでよい。
文字種のチェックには悩みどころがある。どのような正規表現を使うのが適切かという点だ。読みやすく、かつ速い正規表現が知りたい。
さて、文字種チェック用の正規表現は2種類に大別できる。
- 禁止文字が1文字でも含まれればマッチ
- 許容文字のみで構成されていればマッチ
具体的には下記のようなものだ。制御文字（定義は前回の日記を参照）を禁じ、ただし改行とタブは認める例である。
- /[\p{C}\p{Zl}\p{Zp}&&[^\t\r\n]]/u
- /\A[[^\p{C}\p{Zl}\p{Zp}]\t\r\n]*\z/u
どちらも意図は明確で、読みやすさは変わらない。そう私の目には映る。となれば、速いほうが適切な正規表現ということになる。
どちらの正規表現が速いか、ベンチマークを取ってみる。環境はRuby 1.9.2-p290である。
比較する正規表現
2番の正規表現ではバックトラックを避けることもできる。独占的量指定子を使う方法だ。興味のある方は「404 Blog Not Found:regexp - possessive quantifier (独占的|絶対最大)量指定子とは何か?」を参照されたい。
バックトラックを避ける書き方を含め、下記3パターンの速度を比較する。
| 名前 | パターン | 意図 |
|---|---|---|
| regexp1 | /[\p{C}\p{Zl}\p{Zp}&&[^\t\r\n]]/u | 禁止文字が1文字でも含まれればマッチ |
| regexp2 | /\A[[^\p{C}\p{Zl}\p{Zp}]\t\r\n]*\z/u | 許容文字のみで構成されていればマッチ |
| regexp2+ | /\A[[^\p{C}\p{Zl}\p{Zp}]\t\r\n]*+\z/u | 許容文字のみで構成されていればマッチ（バックトラックなし） |
マッチ対象文字列のパターン
マッチ対象文字列は50文字、500文字、5000文字の3パターンを使う。文字数によってマッチに要する速度が変わると予想されるためだ。
また、禁止文字の位置によってもマッチの速度は変わる。禁止文字が先頭に来るケース、末尾に来るケース、含まれないケースの3パターンを調べれば充分だろう。禁止文字は何でもよいのだが、とりあえずNUL（\0）を使う。
文字数が3パターン、禁止文字の位置が3パターンで、全部で9パターンになる。下記の表記を用いれば「50^」「50$」「50x」「500^」「500$」「500x」「5000^」「5000$」「5000x」の9つだ。
| 表記 | 意味 | n=5のときの表記 | n=5のときの文字列 |
|---|---|---|---|
| n^ | NULが先頭に来るn文字の文字列 | 5^ | "\0aaaa" |
| n$ | NULが末尾に来るn文字の文字列 | 5$ | "aaaa\0" |
| nx | NULが含まれないn文字の文字列 | 5x | "aaaaa" |
ベンチマーク用スクリプト
ベンチマークには下記のスクリプトを使う。マッチ対象文字列の文字数（n）を引数で渡せるようにした。ファイル名は何でもよいが、bm.rb としておく。
require 'benchmark' regexps = { "regexp1 " => /[\p{C}\p{Zl}\p{Zp}&&[^\t\r\n]]/u, "regexp2 " => /\A[[^\p{C}\p{Zl}\p{Zp}]\t\r\n]*\z/u, "regexp2+" => /\A[[^\p{C}\p{Zl}\p{Zp}]\t\r\n]*+\z/u } n = ARGV[0].to_i strings = { "#{n}^" => "\0" + "a"*(n-1), # e.g. "5^" => "\0aaaa" "#{n}$" => "a"*(n-1) + "\0", # e.g. "5$" => "aaaa\0" "#{n}x" => "a"*n # e.g. "5x" => "aaaaa" } strings.each do |str_type, str| puts str_type Benchmark.bm(10) do |bm| regexps.each do |re_type, re| bm.report("#{re_type}: "){1.upto(100000){re === str}} end end puts "-" * 55 end
ベンチマークの結果
マッチ対象文字列が50文字の場合
$ ruby bm.rb 50
50^
user system total real
regexp1 : 0.060000 0.000000 0.060000 ( 0.056586)
regexp2 : 0.060000 0.000000 0.060000 ( 0.063264)
regexp2+: 0.070000 0.000000 0.070000 ( 0.065915)
-------------------------------------------------------
50$
user system total real
regexp1 : 0.340000 0.000000 0.340000 ( 0.351705)
regexp2 : 0.250000 0.000000 0.250000 ( 0.245143)
regexp2+: 0.200000 0.000000 0.200000 ( 0.203424)
-------------------------------------------------------
50x
user system total real
regexp1 : 0.270000 0.000000 0.270000 ( 0.268856)
regexp2 : 0.190000 0.000000 0.190000 ( 0.189364)
regexp2+: 0.200000 0.000000 0.200000 ( 0.198914)
-------------------------------------------------------
マッチ対象文字列が500文字の場合
$ ruby bm.rb 500
500^
user system total real
regexp1 : 0.050000 0.000000 0.050000 ( 0.053325)
regexp2 : 0.070000 0.000000 0.070000 ( 0.065296)
regexp2+: 0.060000 0.000000 0.060000 ( 0.068444)
-------------------------------------------------------
500$
user system total real
regexp1 : 2.580000 0.000000 2.580000 ( 2.588114)
regexp2 : 2.120000 0.000000 2.120000 ( 2.124538)
regexp2+: 1.440000 0.000000 1.440000 ( 1.435810)
-------------------------------------------------------
500x
user system total real
regexp1 : 2.090000 0.010000 2.100000 ( 2.098699)
regexp2 : 1.440000 0.000000 1.440000 ( 1.436356)
regexp2+: 1.890000 0.000000 1.890000 ( 1.904694)
-------------------------------------------------------
マッチ対象文字列が5000文字の場合
$ ruby bm.rb 5000
5000^
user system total real
regexp1 : 0.050000 0.000000 0.050000 ( 0.046017)
regexp2 : 0.050000 0.000000 0.050000 ( 0.050167)
regexp2+: 0.050000 0.000000 0.050000 ( 0.051950)
-------------------------------------------------------
5000$
user system total real
regexp1 : 21.100000 0.000000 21.100000 ( 21.110980)
regexp2 : 17.960000 3.350000 21.310000 ( 21.442088)
regexp2+: 14.350000 0.000000 14.350000 ( 14.356223)
-------------------------------------------------------
5000x
user system total real
regexp1 : 21.960000 0.000000 21.960000 ( 22.012767)
regexp2 : 14.750000 3.240000 17.990000 ( 17.993943)
regexp2+: 14.570000 0.000000 14.570000 ( 14.578166)
-------------------------------------------------------
