[Guido]
> The key seems to be:
Except none of that quoted text (which I'll skip repeating) gives the
slightest clue as to _why_ it may be an improvement. So you split the
needle into two pieces. So what? What's the _point_? Why would
someone even imagine that might help?
Why is one half then searched right to left, but the other half left
to right? There's actually "a reason" for searching the right half
left to right, but because the shift on a mismatch in the left half is
a constant ("per(x)") independent of the mismatching position, it's
actually irrelevant in which order the left half's characters are
compared (well, at least in some variations of these newer
algorithms). Over-specification can be actively misleading too.
What's the key idea? "Split the needle into two pieces" is a key
_step_, not a key _insight_.
> I need a Python version though.
Dennis wrote one for his first stab, which you can download from the
bug report (it's attached there as fastsearch.py).
On the bug report's data, running that under CPython 3.9,0 on my box
reduced the time from about 3 1/2 hours to about 20 seconds. Running
it under PyPy, to under one second (and the current C implementation
under 0.1 second).
> I am not able to dream up any hard cases -- like other posters, my own
> use of substring search is usually looking for a short string in a relatively
> short piece of text. I doubt even the current optimizations matter to my uses.
They probably do, but not dramatically. Would you, e.g., notice a
factor of 2 either way in those cases? A factor of 4? Of 10? When
Fredrik first wrote this code, he routinely saw factors of 2 to 10
speedup on all sorts of string-searching benchmarks, both contrived
and "natural". The speedups were especially pronounced for Unicode
strings at the time, where skipping futile Unicode character
comparisons could be more valuable than when skipping (shorter)
single-byte comparisons.
Should also note that the fixed string searching code is also used as
a subroutine by parts of our regexp implementation, by str.count(),
str.replace(), similar `bytes` operations, and so on.
> What are typical hard cases used for?
It's kinda like asking what typical hard rounding cases for pow() are
used for ;-) They aren't deliberate. They "just happen", typically
when a pattern and the text to search contain self-similarities "but
with glitches". Search the string
text = "X" * 10_000_000
for
needle = "X" * 1_000_000
Easy! It matches at once. But now tack "Y" on to the end of the
needle. Then it's impossible to match. Brute force search first
finds a prefix match at text{; 1000000] but then fails to match the
trailing "Y". So brute force uses another million compares to match
the prefix at text[1 : 1000001]. But again fails to match the trailing
"Y". Then another million plus 1 compares to fail to match starting
at index 2, and again at index 3, and again at index 4, ... it
approaches a trillion comparisons before it finally fails.
The current code starts comparing at the right end of each trial
position first. Then an "X" from the text and the needle's trailing
"Y" mismatch at once. That's a million times faster.
Here's a simple case where the current code is horribly slow, because
neither "right-to-left" nor any of its preprocessing tricks do any
good at all. Even Daniel Sunday's full-blown algorithm[1] (which the
current code strips down _almost_ to the point of non-existence)
wouldn't help (unless it used a variant I've never actually seen that
compared the rarest pattern character first):
("X" * 10_000_000).find("X" * 500_000 + "Y" + "X" * 500_000)
The newer code returns -1 seemingly instantly.
> DNA search? (That would be cool!)
It can certainly help. Self-similarities are bound to be common in
long strings from a 4-character alphabet (ACGT). But, to be fair,
serious work with genomes typically invests in building a giant suffix
tree (or enhanced suffix array) for each cataloged sequence to be
searched. No preprocessing of needles is needed then to guarantee
worst-case efficient searches of many kinds (including things like
finding the longest adjacent repeated subsequences, more like a regexp
(.+)\1 kind of search).
But the new code could quite plausibly speed more casual prototyping
of such explorations.
[1] https://dl.acm.org/doi/abs/10.1145/79173.79184
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/XUP6S2IVJAW5K2NSHZ7UOKN5YQFNUWVQ/
Code of Conduct: http://python.org/psf/codeofconduct/
