CODEWITHSUNDEEP
pythonregex
bbambbam sh2ee2
bbambbam sh2ee2

Reputation: 93

Python Regex takes so long in some cases

I compiled the following pattern 

pattern = re.compile(
    r"""
    (?P<date>.*?)
    \s*
    (?P<thread_id>\w+)
    \s*PACKET\s*
    (?P<identifier>\w+)
    \s*
    (?P<proto>\w+)
    \s*
    (?P<indicator>\w+)
    \s*
    (?P<ip>\d+\.\d+\.\d+\.\d+)
    \s*
    (?P<xid>\w+)
    \s*
    (?P<q_r>.*?)
    \s*\[
    (?P<flag_hex>[0-9]*)
    \s*
    (?P<flag_char_code>.*?)
    \s*
    (?P<status>\w+)
    \]\s*
    (?P<record>\w+)
    \s*
    \.(?P<domain>.*)\.
    """, re.VERBOSE
    )

to work with this string

2/1/2014 9:34:29 PM 05EC PACKET 00000000025E97A0 UDP Snd 10.10.10.10 ebbe R Q [8381 DR NXDOMAIN] A (1)9(1)a(3)c-0(11)19-330ff801(7)e0400b1(4)15e0(4)1ca7(4)2f4a(3)210(1)0(26)841f75qnhp97z6jknf946qwfm5(4)avts(6)domain(3)com(0)

And it successfully works 

In [4]: pattern.findall(re.sub('\(\d+\)', '.', x))
Out[4]: 
[('2/1/2014 9:34:29 PM',
  '05EC',
  '00000000025E97A0',
  'UDP',
  'Snd',
  '10.10.10.10',
  'ebbe',
  'R Q',
  '8381',
  'DR',
  'NXDOMAIN',
  'A',
  '9.a.c-0.19-330ff801.e0400b1.15e0.1ca7.2f4a.210.0.841f75qnhp97z6jknf946qwfm5.avts.domain.com')]

The issue is that it takes so long in some cases, any idea how to enhance the pattern for consuming time.

Upvotes: 2

Views: 1718

Answers (2)

Casimir et Hippolyte
Casimir et Hippolyte

Reputation: 89557

You can improve your pattern with:

(?P<domain>\w+(?:[-.]\w+)*)
(?P<date>\d{1,2}/\d{1,2}/\d{4} \d{1,2}:\d{1,2}:\d{1,2} [AP]M)
(?P<q_r>[^[]*)

You need a more explicit subpattern for flag_char_code too, the goal is to describe the content of each group to reduce the regex engine work and avoid backtracking.

Upvotes: 1

JDB
JDB

Reputation: 25810

Yep, you've got yourself a case of catastrophic backtracking, also known as an "evil regex", here:

\s*
(?P<q_r>.*?)
\s*

Here:

\s*
(?P<flag_char_code>.*?)
\s*

And here:

\s*
\.(?P<domain>.*)\.

Replacing .* with \S* should do the trick.

For more information about what an evil regex is and why it's evil, check out this question:
How can I recognize an evil regex?

Upvotes: 6

Related Questions