Mailing List Archive

[Tim]
> ...
> Alas, the higher preprocessing costs leave the current PR slower in "too
> many" cases too, especially when the needle is short and found early
> in the haystack. Then any preprocessing cost approaches a pure waste
> of time.

But that was this morning. Since then, Dennis changed the PR to back
off to the current code when the needle is "too small". There are very
few cases we know of now where the PR code is slower at all than the
current code, none where it's dramatically slower, many where it's
significantly faster, and some non-contrived cases where it's
dramatically faster (for example, over a factor of 10 in
stringbench.py's "late match, 100 characters" forward-search tests,
and especially beneficial for Unicode (as opposed to bytes)). Then
there are the pathological cases like in the original issue report,
where it's multiple orders of magnitude faster (about 3 1/2 hours to
under a tenth of a second in the issue report's case).

Still waiting for someone who thinks string search speed is critical
in their real app to give it a try. In the absence of that, I endorse
merging this.
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@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/5K2ISKORAH327WLQ43QG5QMPWXNHMFTC/
Code of Conduct: http://python.org/psf/codeofconduct/

On 17/10/20 3:26 pm, Tim Peters wrote:
> Tal Einat posted earlier that he was keen to try to work up a clear
> explanation, and I look forward to that. All the expositions I've
> found of this algorithm so far are hard to approach.

Maybe Mathologer or 3blue1brown could be persuaded to help?
They seem to have a knack for making tricky stuff understandable.

--
Greg
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@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/BE3B7K5BTKCJQ63L6RFHW6ZPSQEG67OQ/
Code of Conduct: http://python.org/psf/codeofconduct/

> On Oct 17, 2020, at 2:40 PM, Tim Peters <tim.peters@gmail.com> wrote:
>
> Still waiting for someone who thinks string search speed is critical
> in their real app to give it a try. In the absence of that, I endorse
> merging this.

Be bold. Merge it. :-)


Raymond
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@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/ZHFE4H5RCCRW6XTYLNXOBP2FURZ2VIKW/
Code of Conduct: http://python.org/psf/codeofconduct/