From: "Bartosz Dziewoński" <matma.rex@...>
Date: 2012-03-14T05:42:27+09:00
Subject: Re: Problem replacing $data[abc] with $data['abc'] using gsub

2012/3/13 Brian Candler <b.candler@pobox.com>:
> Jan E. wrote in post #1051180:
>> The part ".*?" of the regular expression is very inefficient
>
> Is it? Have you measured it?
>
>>, because it
>> will at first consume every character until the end of the line and then
>> try to find the minimum of characters needed.
>
> Does it? There are many implementations of ruby, which particular one(s)
> are you referring to?
>
> Your argument suggests that
>
>    /(.+?)(.+?)(.+?)(.+?)(.+?)/ =~ "a"*1_000_000
>
> would be extremely inefficient, but actually it runs very fast for me.
>
> So let's demonstrate if you are right or wrong:
>
> <snip>

Sorry, but you're both wrong. :) The expression, as far as I know,
*will not* first consume eveyrthing, and then back off (or at least
this is implementation-defined). Such regexps can, however, be slow.
(Although .+ can be slow as well.)

Let's try something a tiny bit more complicated (but still simple).

irb(main):001:0> re = /.+?a.+?b/
=> /.+?a.+?b/
irb(main):002:0> s = "ac"*1_000_000 + "b"; nil
=> nil
irb(main):003:0> s =~ re
=> 0

This run fasts. Now, what if it can't match?

irb(main):004:0> s = "ac"*1_000_000; nil
=> nil
irb(main):005:0> s =~ re

I have no idea what the output is - it's been running for a few
minutes... the same happens if you substitute .+? with .+.

This is a bad case of catastrophic backtracking -
http://www.regular-expressions.info/catastrophic.html - and stems from
the fact that matching a regex to a string is asymptotically
exponential.

In short - you should never use .+ or .+?, unless you have a very good
reason or know precisely what kinds of input you will get.