Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python@mrabarnett.plus.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.002
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'url:pypi': 0.03; 'matches': 0.07; '"if': 0.09; 'line:': 0.09; 'skip:/ 10': 0.09; 'subject:Why': 0.09; 'runs': 0.10; 'python': 0.11; '(about': 0.16; '2.7.3': 0.16; 'from:addr:mrabarnett.plus.com': 0.16; 'from:addr:python': 0.16; 'from:name:mrab': 0.16; 'message- id:@mrabarnett.plus.com': 0.16; 'regex,': 0.16; 'roy': 0.16; 'subject:slow': 0.16; ':-)': 0.16; 'wrote:': 0.18; 'module': 0.19; 'machine': 0.22; 'input': 0.22; 'import': 0.22; 'print': 0.22; 'header:User-Agent:1': 0.23; '2.1': 0.24; "i've": 0.25; 'header :In-Reply-To:1': 0.27; "doesn't": 0.30; "i'm": 0.30; 'code': 0.31; 'lines': 0.31; '1.3': 0.31; 'file': 0.32; 'figure': 0.32; 'skip:- 30': 0.32; 'run': 0.32; 'url:python': 0.33; 'running': 0.33; "i'd": 0.34; 'info': 0.35; 'add': 0.35; 'ubuntu': 0.36; 'doing': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'should': 0.36; 'seconds': 0.37; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'skip:p 20': 0.39; 'how': 0.40; 'length': 0.61; 'full': 0.61; 'first': 0.61; 'header:Reply-To:1': 0.67; 'smith': 0.68; 'reply-to:no real name:2**0': 0.71; 'million': 0.74; 'reply-to:addr:python.org': 0.84
X-CM-Score: 0.00
X-CNFS-Analysis: v=2.1 cv=KrN0hwmN c=1 sm=1 tr=0 a=0nF1XD0wxitMEM03M9B4ZQ==:117 a=0nF1XD0wxitMEM03M9B4ZQ==:17 a=0Bzu9jTXAAAA:8 a=oyR3mlnJdzkA:10 a=ynY2aRLGfR4A:10 a=ihvODaAuJD4A:10 a=OUOv7kDek9cA:10 a=8nJEP1OIZ-IA:10 a=EBOSESyhAAAA:8 a=8AHkEIZyAAAA:8 a=APIjv3kaCL4A:10 a=tOTjio7LiH13hgUYb5EA:9 a=KLsogM8rKWwGpqsg:21 a=7gzI3M8SF_ku5MaE:21 a=wPNLvfGTeEIA:10
X-AUTH: mrabarnett:2500
Date: Tue, 18 Jun 2013 18:31:51 +0100
From: MRAB <python@mrabarnett.plus.com>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130509 Thunderbird/17.0.6
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Why is regex so slow?
References: <kpq2r9$gg6$1@panix2.panix.com>
In-Reply-To: <kpq2r9$gg6$1@panix2.panix.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: python-list@python.org
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.3548.1371576696.3114.python-list@python.org>
Lines: 55
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1371576696 news.xs4all.nl 15981 [2001:888:2000:d::a6]:41374
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:48647

On 18/06/2013 17:45, Roy Smith wrote:
> I've got a 170 MB file I want to search for lines that look like:
>
> [2010-10-20 16:47:50.339229 -04:00] INFO (6): songza.amie.history - ENQUEUEING: /listen/the-station-one
>
> This code runs in 1.3 seconds:
>
> ------------------------------
> import re
>
> pattern = re.compile(r'ENQUEUEING: /listen/(.*)')
> count = 0
>
> for line in open('error.log'):
>      m = pattern.search(line)
>      if m:
>          count += 1
>
> print count
> ------------------------------
>
> If I add a pre-filter before the regex, it runs in 0.78 seconds (about
> twice the speed!)
>
> ------------------------------
> import re
>
> pattern = re.compile(r'ENQUEUEING: /listen/(.*)')
> count = 0
>
> for line in open('error.log'):
>      if 'ENQ' not in line:
>          continue
>      m = pattern.search(line)
>      if m:
>          count += 1
>
> print count
> ------------------------------
>
> Every line which contains 'ENQ' also matches the full regex (61425
> lines match, out of 2.1 million total).  I don't understand why the
> first way is so much slower.
>
> Once the regex is compiled, you should have a state machine pattern
> matcher.  It should be O(n) in the length of the input to figure out
> that it doesn't match as far as "ENQ".  And that's exactly how long it
> should take for "if 'ENQ' not in line" to run as well.  Why is doing
> twice the work also twice the speed?
>
> I'm running Python 2.7.3 on Ubuntu Precise, x86_64.
>
I'd be interested in how the 'regex' module 
(http://pypi.python.org/pypi/regex) compares. :-)