bpo-41972: Use the two-way algorithm for string searching #22904
Conversation
Objects/stringlib/fastsearch.h
Outdated
| it has actually checked for matches, but didn't find any. callers | ||
| beware! */ | ||
|
|
||
| /* If the needle is long enough, use Crochemore and Perrin's Two-Way | ||
| algorithm, which has guaranteed O(n) runtime. Also compute a table | ||
| of shifts to sometimes achieve O(n/m) runtime in the best cases. */ |
There was a problem hiding this comment.
For the last two lines, suggest instead:
algorithm, which has worst-case O(n) runtime, and best case O(n/k). Also compute a table of shifts to achieve O(n/k) in more cases, and to often (data dependent) deduce larger shifts than pure C&P can deduce.
Co-authored-by: Tim Peters <tim.peters@gmail.com>
|
This PR is stale because it has been open for 30 days with no activity. Remove stale label or comment or this will be closed in 5 days |
|
@github-actions I think this should stay open |
|
Absolutely keep it open! I've been buried under other stuff, but am still keen to get this merged. |
|
We've configured it so that GitHub action doesn't close the PR, so don't worry. I will see about adjusting that message. |
|
If @tim-one approves we might get this into alpha 6 which goes out Monday. @pablogsal what do you think? |
There was a problem hiding this comment.
As briefly explained on BPO, I'd very much like to see this get in, but can't make the time needed for an in-depth review for the foreseeable future. So I'm approving this based on the last serious review I did (some months ago, alas). It would be great to get a more recent review, though.
Yup, it should not be any problem. As I have a SC meeting on Monday I will probably start the release a bit later than usual (around 7PM London time). I could also hold it a bit more if needed :) |
|
To be explicit here, am I "it" for hitting the "Squash and merge" button if/when the time comes for that? Fine by me if so, just want to be clear so it doesn't get dropped due to mistaken assumptions. If I am "it", and don't hear more, I'll hit the button tomorrow afternoon (about 18 hours from now, approximately 19:00 CST Saturday, so about 13:00 CST Sunday). |
|
W00t! This deserves a note in what's new as well (Doc/whatsnew/3.10.rst). |
https://bugs.python.org/issue41972