search

lcompilers / lpython

Python compiler
https://lpython.org/
Other
1.5k stars 158 forks source link

Improved str.count() algorithm using the Knuth-Morris-Pratt algorithm #2530

Closed advikkabra closed 7 months ago

advikkabra commented 7 months ago

Implemented the Knuth-Morris-Pratt algorithm for str.count(), similar to the str.find() implementation. This should improve speed significantly in many cases.

advikkabra commented 7 months ago

As an aside, as recommended by #2355, we can improve these algorithms further and benchmark them if need be. There may be variations of the Boyer-Moore algorithm which work better, as the issue suggests, but I have used KMP as it is previously used for the string find method. I can work on testing and benchmarking them if the current algorithms are to be changed.

CPython implementation Blog post explaining more

advikkabra commented 7 months ago

@certik Could you review this PR?