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
📜🤖 Added by blurb_it.
  • Loading branch information
@blurb-it
blurb-it[bot] authored Oct 12, 2020
commit 658038d575e519c05d9b734b0f5f3f7ea988193b
1 change: 1 addition & 0 deletions Misc/NEWS.d/next/Core and Builtins/2020-10-12-23-46-49.bpo-41972.0pHodE.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
Substring search functions such as ``str1 in str2`` and ``str2.find(str1)`` now use the "Two-Way" string comparison algorithm to avoid quadratic behavior in the worst cases.