Help us understand the problem. What is going on with this article?

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

More than 3 years have 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)

ちゃんと差がでてます。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした