Path: csiph.com!usenet.pasdenom.info!nntpfeed.proxad.net!news.muarf.org!news.roellig-ltd.de!open-news-network.org!border2.nntp.ams1.giganews.com!border1.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: Find in ipython3
Date: Sun, 07 Jun 2015 12:27:05 +0200
Organization: None
References: <87y4k2hyvf.fsf@Equus.decebal.nl> <mailman.177.1433448836.13271.python-list@python.org> <87bnguhbec.fsf@Equus.decebal.nl> <874mmlqhul.fsf@Equus.decebal.nl> <mailman.215.1433588892.13271.python-list@python.org> <87sia4ox8h.fsf@Equus.decebal.nl>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8Bit
User-Agent: KNode/4.13.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.236.1433672873.13271.python-list@python.org>
Lines: 113
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:92225

Cecil Westerhof wrote:

> On Saturday  6 Jun 2015 13:07 CEST, Laura Creighton wrote:
> 
>> The !find version is C code optimised to do one thing, find files in
>> your directory structure, which happens to be what you want to do.
>> General regular expression matching is harder.
>>
>> Carl Friedrich Bolz investigated regular expression algorithms and
>> their implementation to see if this is the sort of task that a JIT
>> can improve. He blogged about it in 2 posts (part1 and part2). There
>> are benchmarks for part2. Benchmarks in part2.
>>
>> see:
>> http://morepypy.blogspot.se/2010/05/efficient-and-elegant-regular.html
>> http://morepypy.blogspot.se/2010/06/jit-for-regular-expression-matching.html
>>
>> You may get faster results if you use Matthew Barnett's replacement
>> for re here: https://pypi.python.org/pypi/regex
>>
>> You will get faster results if you build your IPython shell to use
>> PyPy, but I would still be very surprised if it beat the C program
>> find.
> 
> I have to look into that. But I prefer to write a version that can be
> used by ‘everyone’.
> 
> It is of-course not a very big program. The difference is significant,
> but I do not use find that much. And if it is significant I still can
> use the shell version.
> 
> There is no gain to get in standard Python? By switching from fnmatch
> to re I got almost a speed gain of two. So I was wondering if I could
> do more.

Just wait for Python 3.5. The switch from os.listdir() to the (new) 
os.scandir() in the implementation of os.walk() is likely to improve the 
situation: 

$ cat findfiles.py                    
import fnmatch
import os
import re
import subprocess
import time


def find_re(root, pattern, ignore_case=False):
    match = re.compile(
        fnmatch.translate(pattern),
        re.IGNORECASE if ignore_case else 0).match

    results = []
    for path, _folders, files in os.walk(root):
        for filename in files:
            if match(filename):
                results.append(os.path.join(path, filename))
    return results


def find_sp(
        root, pattern, ignore_case=False,
        encoding="utf-8", errors="surrogateescape"):

    name_opt = "-iname" if ignore_case else "-name"
    matches = subprocess.Popen(
        ["find", root, name_opt, pattern, "-print0"], stdout=subprocess.PIPE
    ).communicate()[0].decode(encoding, errors=errors).split("\0")
    assert len(matches[-1]) == 0
    del matches[-1]
    return matches


def measure(f, *args):
    start = time.time()
    try:
        return f(*args)
    finally:
        end = time.time()
        print("{}{}".format(f.__name__, args), end - start)


def main():
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument("root")
    parser.add_argument("pattern")
    parser.add_argument("-i", "--ignore-case", action="store_true")
    args = parser.parse_args()

    a = measure(find_re, args.root, args.pattern, args.ignore_case)
    b = measure(find_sp, args.root, args.pattern, args.ignore_case)
    measure(find_re, args.root, args.pattern, args.ignore_case)
    assert sorted(a) == sorted(b)
    print(len(a), "matches")


if __name__ == "__main__":
    main()

$ python3.4 findfiles.py . '*a*.PY' -i
find_re('.', '*a*.PY', True) 0.14614605903625488
find_sp('.', '*a*.PY', True) 0.043445587158203125
find_re('.', '*a*.PY', True) 0.16485309600830078
1454 matches

$ python3.5 findfiles.py . '*a*.PY' -i
find_re('.', '*a*.PY', True) 0.07263660430908203
find_sp('.', '*a*.PY', True) 0.04418468475341797
find_re('.', '*a*.PY', True) 0.07320952415466309
1454 matches