RetroSearch Browse

Wed Feb 16 23:00:54 CET 2005 · http://mail.python.org/pipermail/python-dev/2005-February/051606.html

Irmen de Jong wrote:
> There's the Boyer-Moore string search algorithm which is
> allegedly much faster than a simplistic scanning approach,
> and I also found this: http://portal.acm.org/citation.cfm?id=79184
> So perhaps there's room for improvement :)

The problem is setup vs. run.  If the question is 'ab in 'rabcd',
Boyer-Moore and other fancy searches will be swamped with prep time.
In Fred's comparison with re, he does the re.compile(...) outside of
the timing loop.  You need to decide what the common case is.
The longer the thing you are searching in, the more one-time-only
overhead you can afford to reduce the per-search-character cost.

--Scott David Daniels
Scott.Daniels at Acm.Org

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://mail.python.org/pipermail/python-dev/2005-February/051606.html below:

[Python-Dev] Re: string find(substring) vs. substring in string