Skip to content

bpo-41972: Use the "Two-Way" algorithm when searching for long substrings #22679

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
sweeneyde wants to merge 21 commits into from
Closed

bpo-41972: Use the "Two-Way" algorithm when searching for long substrings #22679

Changes from 1 commit
Commits
Show all changes
21 commits
Select commit Hold shift + click to select a range
899f289
initial implementation
sweeneyde Oct 11, 2020
743a382
refactoring
sweeneyde Oct 12, 2020
fdb6800
formatting fixes
sweeneyde Oct 12, 2020
737ac8a
add shift and bloom
sweeneyde Oct 12, 2020
658038d
📜🤖 Added by blurb_it.
blurb-it[bot] Oct 12, 2020
b62e4c6
add alternating find_char calls
sweeneyde Oct 14, 2020
25a61fb
USe a shift table
sweeneyde Oct 14, 2020
64b9a0a
compute a shift for the last character
sweeneyde Oct 14, 2020
5568ca2
Remove unnecessary special case
sweeneyde Oct 14, 2020
f2054e0
Merge branch 'two-way' of https://github.com/sweeneyde/cpython into t…
sweeneyde Oct 14, 2020
415f492
removed unneeded shift computation
sweeneyde Oct 15, 2020
06c3678
restore original code with special case for long needles
sweeneyde Oct 17, 2020
89bdc34
Minor code cleanups
sweeneyde Oct 17, 2020
9d7bbc3
Restore comment and fix typo
sweeneyde Oct 17, 2020
c331307
Update 2020-10-12-23-46-49.bpo-41972.0pHodE.rst
sweeneyde Oct 17, 2020
66377ce
Add test cases catered to the new algorithm
sweeneyde Oct 17, 2020
e718e5a
Merge branch 'two-way' of https://github.com/sweeneyde/cpython into t…
sweeneyde Oct 17, 2020
cf4e398
Fix typo
sweeneyde Oct 17, 2020
3933992
add a cutoff for haystack length
sweeneyde Oct 19, 2020
c8e54c6
simplify a couple of lines
sweeneyde Oct 19, 2020
8208853
Add better threshholds
sweeneyde Oct 19, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Restore comment and fix typo
  • Loading branch information
@sweeneyde
sweeneyde committed Oct 17, 2020
commit 9d7bbc38ddcdc640779e511f785a461d08cadf14
9 changes: 8 additions & 1 deletion Objects/stringlib/fastsearch.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,6 +21,13 @@
https://bugs.python.org/issue41972
*/

/* note: fastsearch may access s[n], which isn't a problem when using
Python's ordinary string types, but may cause problems if you're
using this code in other contexts. also, the count mode returns -1
if there cannot possible be a match in the target string, and 0 if
it has actually checked for matches, but didn't find any. callers
beware! */

#define FAST_COUNT 0
#define FAST_SEARCH 1
#define FAST_RSEARCH 2
Expand Down Expand Up @@ -581,7 +588,7 @@ FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,
}

/* Short needles use Fredrik Lundh's Horspool/Sunday hybrid
aglorithm for less overhead. */
algorithm for less overhead. */
const STRINGLIB_CHAR *ss = s + m - 1;
const STRINGLIB_CHAR *pp = p + m - 1;

Expand Down