By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,627 Members | 1,211 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,627 IT Pros & Developers. It's quick & easy.

Python RegExp

P: n/a
I have a string which I wish to match using RE, however when I run my
comparison (using the match method) on my machine it never returns,
using the CPU fully.

The code is (very simply):

------------------------------
import re

buffer = r"#1 1 550 111 SYNC_PEER RES
<YP>syncpeers=(id=54325432;add=10." \

"0.0.1;port=89;up=89),(id=97899;add=10.0.0.1;port= 543;up=543)," \
"(id=54325432;add=10.0.0.1;port=89;up=8"

p = re.compile(r'#(?P<tran>[0-9]+\s)(?P<sess>[0-9]+\s)' \
+ '(?P<ndto>[0-9]+\s)(?P<ndfr>[0-9]+\s)' \
+ '(?P<cmd>[a-zA-Z_]+\s)(?P<dir>[a-zA-Z_]+)' \
+ '(?P<parm>(\s<[a-zA-Z]+>(\s*[a-zA-Z]+=[a-zA' \
+ '-Z0-9.,=();]+\s*)+<[a-zA-Z]+>)*)#(?P<left>.*$)')

print "starting the match"
rst = (p.match (buffer) != None)
print "finishing the match"
--------------------------------

Should this every actually happen? Regardless of whether the statment
matches or not, surely it should do this?

Jul 18 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
da***********@gmail.com wrote:
I have a string which I wish to match using RE, however when I run my
comparison (using the match method) on my machine it never returns,
using the CPU fully.

The code is (very simply):

------------------------------
import re

buffer = r"#1 1 550 111 SYNC_PEER RES
<YP>syncpeers=(id=54325432;add=10." \

"0.0.1;port=89;up=89),(id=97899;add=10.0.0.1;port= 543;up=543)," \
"(id=54325432;add=10.0.0.1;port=89;up=8"

p = re.compile(r'#(?P<tran>[0-9]+\s)(?P<sess>[0-9]+\s)' \
+ '(?P<ndto>[0-9]+\s)(?P<ndfr>[0-9]+\s)' \
+ '(?P<cmd>[a-zA-Z_]+\s)(?P<dir>[a-zA-Z_]+)' \
+ '(?P<parm>(\s<[a-zA-Z]+>(\s*[a-zA-Z]+=[a-zA' \
+ '-Z0-9.,=();]+\s*)+<[a-zA-Z]+>)*)#(?P<left>.*$)')

print "starting the match"
rst = (p.match (buffer) != None)
print "finishing the match"
--------------------------------

Should this every actually happen? Regardless of whether the statment
matches or not, surely it should do this?


surely the following should never be slow?

n = len(s)
for a in range(n):
for b in range(n):
for c in range(n):
for d in range(n):
for e in range(n):
... etc ...

(your RE contains several nested and/or related repeat operators,
which forces the poor engine to test zillions of combinations before
giving up. see Friedl's RE book for more information on this)

I suggest using a real parser for this task (or using the RE engine as
a tokenizer, and doing the rest in code; see
http://effbot.org/zone/xml-scanner.htm for more on this)

</F>

Jul 18 '05 #2

P: n/a
On my machine the program finishes in 30 seconds. (it's a 1.5GHz machine)
If the 'parm' group is removed, or if the buffer is shortened, the time
is reduced considerably.

There are "pathological cases" for regular expressions which can take
quite a long time. In the case of your expression, it's happening for
the group 'parm'. I think, but don't know, that each time a candidate
for 'parm' is found, the following '#' (or maybe the second '<'?) is not
found, and it backtracks to try to match 'parm' in a different way,
which involves considering many different combinations (basically, each
'name=' could be the start of a new instance of the first parenthsized
subgroup of <parm>, or it could be part of the character class that
includes [a-zA-Z=])

You may wish to consider using other approaches for parsing this text
than regular expressions.

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)

iD8DBQFCQK+2Jd01MZaTXX0RApByAJ4hIU1RVFWwdOeX28RLwQ H1rSk5awCeJXrE
mhBvK2/gMBghI/VamQfVFYc=
=8+da
-----END PGP SIGNATURE-----

Jul 18 '05 #3

P: n/a
Jeff,

Thanks very much for that, I didn't even consider the option of it
finishing, considering I'm using a much slower machine it was running
for over 2 minutes when I just killed it! I think I get the rest now.

Cheers again,

-David
On Tue, 22 Mar 2005 17:52:22 -0600, Jeff Epler <je****@unpythonic.net> wrote:
On my machine the program finishes in 30 seconds. (it's a 1.5GHz machine)
If the 'parm' group is removed, or if the buffer is shortened, the time
is reduced considerably.

There are "pathological cases" for regular expressions which can take
quite a long time. In the case of your expression, it's happening for
the group 'parm'. I think, but don't know, that each time a candidate
for 'parm' is found, the following '#' (or maybe the second '<'?) is not
found, and it backtracks to try to match 'parm' in a different way,
which involves considering many different combinations (basically, each
'name=' could be the start of a new instance of the first parenthsized
subgroup of <parm>, or it could be part of the character class that
includes [a-zA-Z=])

You may wish to consider using other approaches for parsing this text
than regular expressions.

Jeff

Jul 18 '05 #4

P: n/a
D H
da***********@gmail.com wrote:
I have a string which I wish to match using RE, however when I run my
comparison (using the match method) on my machine it never returns,
using the CPU fully.


In your case it may be simpler to just split the string into groups.
You don't even need regular expressions or a parser.

buff = r"#1 1 550 111 SYNC_PEER RES <YP>syncpeers=(id=54325432;add=10." \
"0.0.1;port=89;up=89),(id=97899;add=10.0.0.1;port= 543;up=543)," \
"(id=54325432;add=10.0.0.1;port=89;up=8)"

tran, sess, ndto, ndf, cmd, dirr, rest = buff.split()

eq = rest.find("=")
parmname = rest[0:eq]
parms = rest[eq+1:].split(",")

for parm in parms:
parmitems = parm[1:-1].split(";")
for item in parmitems:
name, val = item.split("=")
print name, val
print "---"
Jul 18 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.