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

Fredrik Lundh fredrik at pythonware.com
Wed Feb 16 22:50:55 CET 2005

Guido van Rossum wrote:

Which is exactly how s.find() wins this race. (I guess it loses when it's found by having to do the "find" lookup.) Maybe stringcontains should just call stringfindinternal()?

I somehow suspected that "in" did some extra work in case the "find" failed; guess I should have looked at the code instead... I didn't really expect anyone to use a bad implementation of a brute-force algorithm (O(nm)) when the library already contained a reasonably good version of the same algorithm.

And then there's the question of how the re module gets to be faster still; I suppose it doesn't bother with memcmp() at all.

the benchmark cheats (a bit) -- it builds a state machine (KMP-style) in "compile", and uses that to search in O(n) time.

that approach won't fly for "in" and find, of course, but it's definitely possible to make them run a lot faster than RE (i.e. O(n/m) for most cases)...

but refactoring the contains code to use find_internal sounds like a good first step. any takers?

More information about the Python-Dev mailing list