0

This:

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  perl -pe '/^(.*?B(?:A.*?B){30})A/'

takes an astonishing 8 seconds on my machine. I had expected it to take at most a few ms.

This takes < 10 ms:

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
   perl -pe '/^(.*?B(?:A.*?B){30})A/'

How can I make the first go faster?

I will need A and B to be regular expressions i.e. they will not simply be single letters.

  • The code blocks for 8 seconds and <10ms seems the exact same... or am I misreading? – EDubman Apr 23 '18 at 0:15
  • The input is not the same. – Ole Tange Apr 23 '18 at 0:15
  • 1
    I'm somewhat inclined to vote-to-close this question. This seems far too esoteric to be of any use to anyone in the future. And the proposed solution isn't generic to where it might apply to other situations. What is the use case where someone might need to run such a regex on this type of string? Also what is the expected result? There could be other solutions to the actual problem that is trying to be solved. – Patrick Apr 23 '18 at 1:56
  • 1
    @Patrick It is really not about the use case but more about the problem: What are the techniques you can use, when you stumble upon a regexp+input that is slow? The negative look-ahead followed by . is one of those techniques. (It also serves to validate people that they are not crazy when the same regexp takes ms on one string but 8 seconds on another). – Ole Tange Apr 23 '18 at 5:59
  • 1
    @roaima --recend/--recstart with --regexp for GNU Parallel. – Ole Tange Apr 23 '18 at 16:07
1

Use negative look-ahead and .:

perl -pe '/^((?:(?!BA).)*?B(?:A(?:(?!BA).)*?B){30})A/'

Not really pretty, but it works.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.