Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Regex::Reverse tricky test cases

by exussum0 (Vicar)
on May 17, 2005 at 13:13 UTC ( [id://457785]=note: print w/replies, xml ) Need Help??


in reply to Regex::Reverse tricky test cases

For all the "why" people, here's my guess as to why. A regular expression is just a program. It has a start point, then tries to do somethings, back tracks, and returns true if the regexp holds true for some part of the string, depending on how the regexp is written.

By inverting it, you may get a more optimized regexp. It is easier to solve some problems and get an answer. Sometimes it's faster to say what the answer isn't and go by that.

----
Give me strength for today.. I will not talk it away..
Just for a moment.. It will burn through the clouds.. and shine down on me.

Replies are listed 'Best First'.
Re^2: Regex::Reverse tricky test cases
by hv (Prior) on May 18, 2005 at 12:06 UTC

    I know of 3 main reasons to want to reverse a regexp. Firstly it swaps "can't have variable-length lookbehinds" for "can't have variable length lookaheads", and sometimes a variable-length lookbehind is really useful. Secondly, tail-anchored variable-length patterns are difficult to optimise (for much the same reasons as make variable-length lookbehind difficult to support), and reversing makes them head-anchored and optimisable. Thirdly it is an interesting intellectual pursuit that may tell us more about the mathematics of the patterns we express through regexps (and that might in turn supply new insights which would benefit us in unanticipable ways).

    Probably the simplest common example is stripping trailing whitespace with s/\s+\z//, an incantation often liberally sprinkled around people's code. Because there is no specific optimisation that handles this, the runtime will increase with the number of embedded spaces in the text:

    #!/usr/bin/perl -w use Benchmark; our $nonspace = ('abc' x 100) . "\n"; our $space = ('a c' x 100) . "\n"; Benchmark::cmpthese(-1, { space => q{ my $copy = $space; $copy =~ s/\s+\z// }, nonspace => q{ my $copy = $nonspace; $copy =~ s/\s+\z// }, }); Rate space nonspace space 32880/s -- -89% nonspace 300755/s 815% --

    Hugo

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://457785]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (4)
As of 2024-03-29 07:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found