From: Mathieu Bouchard <matju@...>
Date: 2006-07-22T13:12:33+09:00
Subject: Re: Regular-Expressions Problem/Bug

--8323328-1810486933-1153541503=:30944
Content-Type: MULTIPART/MIXED; BOUNDARY="8323328-1810486933-1153541503=:30944"

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--8323328-1810486933-1153541503=:30944
Content-Type: TEXT/PLAIN; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Thu, 20 Jul 2006, Reto Schuettel wrote:

>>> R> res =3D [ /(.*)ABC[y]\#$/,
>>> R>         /(.*)ABC[y]\#/,
>>> R>         /(.*)ABCy\#$/,
>>> R>         /(.*)ABCy\#/ ]
>>>
>>>  remove this `(.*)' it's just useless
>>
>> Oh, yes, you can get that with MatchData#prematch.  That's worth testing
>> to see how that affects performance.
>
> In my case this was my work-around, but it may not work in other cases.
> I'm just wondering if this really is normal/as it should be.

Actually, I found the answer: /foo/ acts like /^(?:.*)foo/, so /(.*)foo/=20
acts like /^(?:.*)(.*)foo/, which is O(LENGTH^2) because the two=20
quantifiers don't talk to each other, and act as nested loops like:

LENGTH.downto(0) {|n|
   (LENGTH-n).downto(0) {|m|
     try to match stuff and break when done
   }
}

To test my hypothesis, I tried /(.*)(.*)/ and it behaved like 3 nested=20
loops, in O(LENGTH^3).

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - t=E9l:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montr=E9al QC Canada
--8323328-1810486933-1153541503=:30944--
--8323328-1810486933-1153541503=:30944--