[Python-bugs-list] [Bug #112521] re match becomes exponentially slow on larger inputs

[noreply@sourceforge.net]

Bug #112521, was updated on 2000-Aug-22 22:46
Here is a current snapshot of the bug.

Project: Python
Category: Modules
Status: Open
Resolution: None
Bug Group: None
Priority: 5
Summary: re match becomes exponentially slow on larger inputs

Details: The following code will run very slowly, using either python 1.5.2 or 1.6b1:

----8<----
import re

s = """

  arp               ARP commands
  class             Classifier commands
  dns               DNS commands
  email             Email commands
  event             User event commands
  frame             Frame Relay commands
  group             Group configuration commands
  help              On-Line help facility
  hl                Host list configuration commands
  hostdb            Host database commands
  image             Image commands
  links             Link commands
  look              Withdraw touch access (go back to look-only access)
  measure           Measurement commands
  mib               MIB commands
  net               Network statistics commands
  partition         Bandwidth partition commands
  policy            Policy commands
  reset             Reset the PacketShaper

"""

r = re.compile ( r"\n\n(\s+.+\n)+\n\n$" )

mo = r.match ( s )

if mo:
        print "groups = %s" % mo.groups()
else:
        print "no match"
----8<----

The above program takes 11 seconds to run on my system. FOr each line that I add in 's', the time DOUBLES. (And halves if I remove lines)


For detailed info, follow this link:
http://sourceforge.net/bugs/?func=detailbug&bug_id=112521&group_id=5470