string find(substring) vs. substring in string
any special reason why "in" is faster if the substring is found, but a lot slower if it's not in there? timeit -s "s = 'not there'*100" "s.find('not there') != -1" 1000000 loops, best of 3: 0.749 usec per loop timeit -s "s = 'not there'*100" "'not there' in s" 10000000 loops, best of 3: 0.122 usec per loop timeit -s "s = 'not the xyz'*100" "s.find('not there') != -1" 100000 loops, best of 3: 7.03 usec per loop timeit -s "s = 'not the xyz'*100" "'not there' in s" 10000 loops, best of 3: 25.9 usec per loop </F> ps. btw, it's about time we did something about this: timeit -s "s = 'not the xyz'*100" -s "import re; p = re.compile('not there')" "p.search(s)" 100000 loops, best of 3: 5.72 usec per loop
Fredrik Lundh wrote:
any special reason why "in" is faster if the substring is found, but a lot slower if it's not in there?
Just guessing here, but in general I would think that it would stop searching as soon as it found it, whereas until then, it keeps looking, which takes more time. But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
On Wed, Feb 16, 2005 at 01:34:16PM -0700, Mike Brown wrote:
time. But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
Assuming stringobject.c:string_contains is the right function, the code looks like this: size = PyString_GET_SIZE(el); rhs = PyString_AS_STRING(el); lhs = PyString_AS_STRING(a); /* optimize for a single character */ if (size == 1) return memchr(lhs, *rhs, PyString_GET_SIZE(a)) != NULL; end = lhs + (PyString_GET_SIZE(a) - size); while (lhs <= end) { if (memcmp(lhs++, rhs, size) == 0) return 1; } So it's doing a zillion memcmp()s. I don't think there's a more efficient way to do this with ANSI C; memmem() is a GNU extension that searches for blocks of memory. Perhaps saving some memcmps by writing if ((*lhs == *rhs) && memcmp(lhs++, rhs, size) == 0) would help. --amk
Assuming stringobject.c:string_contains is the right function, the code looks like this:
size = PyString_GET_SIZE(el); rhs = PyString_AS_STRING(el); lhs = PyString_AS_STRING(a);
/* optimize for a single character */ if (size == 1) return memchr(lhs, *rhs, PyString_GET_SIZE(a)) != NULL;
end = lhs + (PyString_GET_SIZE(a) - size); while (lhs <= end) { if (memcmp(lhs++, rhs, size) == 0) return 1; }
So it's doing a zillion memcmp()s. I don't think there's a more efficient way to do this with ANSI C; memmem() is a GNU extension that searches for blocks of memory. Perhaps saving some memcmps by writing
if ((*lhs == *rhs) && memcmp(lhs++, rhs, size) == 0)
would help.
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 string_contains should just call string_find_internal()? 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. -- --Guido van Rossum (home page: http://www.python.org/~guido/)
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 string_contains should just call string_find_internal()?
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? </F>
A.M. Kuchling wrote:
time. But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
Assuming stringobject.c:string_contains is the right function, the code looks like this:
size = PyString_GET_SIZE(el); rhs = PyString_AS_STRING(el); lhs = PyString_AS_STRING(a);
/* optimize for a single character */ if (size == 1) return memchr(lhs, *rhs, PyString_GET_SIZE(a)) != NULL;
end = lhs + (PyString_GET_SIZE(a) - size); while (lhs <= end) { if (memcmp(lhs++, rhs, size) == 0) return 1; }
So it's doing a zillion memcmp()s. I don't think there's a more efficient way to do this with ANSI C; memmem() is a GNU extension that searches for blocks of memory.
oops. so whoever implemented contains didn't even bother to look at the find implementation... (which uses the same brute-force algorithm, but a better implementation...)
Perhaps saving some memcmps by writing
if ((*lhs == *rhs) && memcmp(lhs++, rhs, size) == 0)
would help.
memcmp still compiles to REP CMPB on many x86 compilers, and the setup overhead for memcmp sucks on modern x86 hardware; it's usually better to write your own bytewise comparision... (and the fact that we're still brute-force search algorithms in "find" is a bit embarrassing -- note that RE outperforms "in" by a factor of five.... guess it's time to finish the split/replace parts of stringlib and produce a patch... ;-) </F>
Mike Brown wrote:
Fredrik Lundh wrote:
any special reason why "in" is faster if the substring is found, but a lot slower if it's not in there?
Just guessing here, but in general I would think that it would stop searching as soon as it found it, whereas until then, it keeps looking, which takes more time. But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
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 :) --Irmen
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@Acm.Org
The longer the thing you are searching in, the more one-time-only overhead you can afford to reduce the per-search-character cost.
Only if you don't find it close to the start. -- --Guido van Rossum (home page: http://www.python.org/~guido/)
Boyer-Moore and variants need a bit of preprocessing on the pattern which makes them great for long patterns but more costly for short ones. On Wed, 16 Feb 2005, Irmen de Jong wrote:
Mike Brown wrote:
Fredrik Lundh wrote:
any special reason why "in" is faster if the substring is found, but a lot slower if it's not in there?
Just guessing here, but in general I would think that it would stop searching as soon as it found it, whereas until then, it keeps looking, which takes more time. But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
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 :)
--Irmen _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/allison%40sumeru.stanford....
Mike Brown wrote:
any special reason why "in" is faster if the substring is found, but a lot slower if it's not in there?
Just guessing here, but in general I would think that it would stop searching as soon as it found it, whereas until then, it keeps looking, which takes more time.
the point was that string.find does the same thing, but is much faster in the "no match" case.
But I would also hope that it would be smart enough to know that it doesn't need to look past the 2nd character in 'not the xyz' when it is searching for 'not there' (due to the lengths of the sequences).
note that the target string was "not the xyz"*100, so the search algorithm surely has to look past the second character ;-) (btw, the benchmark was taken from jim hugunin's ironpython talk, and seems to be carefully designed to kill performance also for more advanced algorithms -- including boyer-moore) </F>
Fredrik Lundh wrote:
(btw, the benchmark was taken from jim hugunin's ironpython talk, and seems to be carefully designed to kill performance also for more advanced algorithms -- including boyer-moore)
Looking for "not there" in "not the xyz"*100 using Boyer-Moore should do about 300 probes once the table is set (the underscores below): not the xyznot the xyznot the xyz... not ther_ not the__ not ther_ not the__ not ther_ ... -- Scott David Daniels Scott.Daniels@Acm.Org
Scott David Daniels wrote:
Looking for "not there" in "not the xyz"*100 using Boyer-Moore should do about 300 probes once the table is set (the underscores below):
not the xyznot the xyznot the xyz... not ther_ not the__ not ther_ not the__ not ther_ ...
yup; it gets into a 9/2/9/2 rut. tweak the pattern a little, and you get better results for BM. ("kill" is of course an understatement, but BM usually works better. but it still needs a sizeof(alphabet) table, so you can pretty much forget about it if you want to support unicode...) </F>
participants (7)
-
A.M. Kuchling -
Dennis Allison -
Fredrik Lundh -
Guido van Rossum -
Irmen de Jong -
Mike Brown -
Scott David Daniels