Ruby
regexp

正規表現のパフォーマンスの話をされても全くピンと来なかった僕は、backtrackに出会いました。

More than 1 year has passed since last update.

社内LTで、ベトナムから来たタイン君から

「ふつう正規表現は長ければ長い方がよい」というお話を聞いて、

http://qiita.com/DinhDuyThanh/items/1b19eba549f3680d3378

「は?..どういうことでしょうか?」 (という状態でした。


例えば

郵便番号「123-4567」にマッチする正規表現として以下の2つを考えてみると、


どちらもマッチします。

/^.*-.*$/    #悪い(表現方法として"短い"けど)

/^\d{3}-\d{4}$/ #良い(表現方法として"長い")


となります。

(もちろん、上のパタンは、デタラメなものも引っかかるので、正しくないけど、そういうのはいったん無視。

感覚的には下の方がよさそうだけど。どういうことですか?


ステップ数を見てみる!

https://regex101.com/#pcre

この素晴らしいサイトを利用します。

123-4567とのマッチングを考えます。

まず、/^\d{3}-\d{4}$/ はこんな感じで、7ステップ

スクリーンショット 2016-05-28 20.06.30.png

一方、/^.*-.*$/ は..12ステップ

スクリーンショット 2016-05-28 20.07.14.png

ということで、.* の方がステップ数が増えてパフォーマンスが悪くなっていそうです。

(実際パフォーマンスはこのステップ数に依存しそうなので、悪くなっていると思います。後で時間測ります。


バックトラック(BACKTRACK)と出会いました。

上のツールを使うことで、正規表現の処理順序が視覚的に理解できます。

左から比較処理をしていくのですが、ステップ3を比較します。

スクリーンショット 2016-05-28 20.29.58.png

スクリーンショット 2016-05-28 20.21.10.png

(\d{3})123とマッチさせて次の比較に移るのに対して、(.*)123-4567にマッチさせます。そして次の比較(-)をします。そしてコケます。

*は貪欲なのです。(The asterisk is greedy.)

そして、123-4567を諦めたアスタリスクは、123-456で再度トライします。そしてまたコケます。そして、次は123-45という具合に進めて行きます。

このようなアルゴリズムを「バックトラッキング(バックトラック法など)」と云います。上のサービスで赤文字で描かれていますね。「BACKTRACK」

*+は、まずは最大限マッチする範囲を広げて、つぎのパターンマッチを考え、ダメだったらひとつ範囲を狭めて再度やり直すわけです。

分かってきました。


1行で同じパタンが繰り返される場合も、もう迷わない。

"name" => "taro"

という行に対して、/".*"/というパターンは、どこにマッチしてるんだ?と、以前は迷っていました。が、backtrackと出会った僕は、もう迷いません。彼(asterisk)は貪欲なので、"name" => "taro" 全体にマッチすることがわかります。


時間を計測してみる

差がでやすように、サンプルをちょっと長くしておりますが。 rubyで調べます。

irb(main):001:0> require 'benchmark'

=> true
irb(main):002:0> Benchmark.bm do |x|
irb(main):003:1* x.report {1000000.times do '123-456-789-123-456-789' =~ /\d{3}-\d{3}-\d{3}-\d{3}-\d{3}-\d{3}/ end}
irb(main):004:1> x.report {1000000.times do '123-456-789-123-456-789' =~ /.*-.*-.*-.*-.*-.*/ end}
irb(main):005:1> end
user system total real
0.680000 0.000000 0.680000 ( 0.692865)
2.800000 0.010000 2.810000 ( 2.821374)

ちゃんと差がでてます。

以上、ありがとうございました!