Rabin-Karp algorithm perfomance

[alisher-matkurbanov]

Your Rabin-Karp algorithm uses python default hash function which is not using rolling hash property that allows to compute hash of next string effectively for constant time. Because of this property RK-algo works for O(n) in average case (when collisions for hash of part of s and hash for pattern don't happen so often). It would be better to improve this implementation.

[cclauss]

Cool. Should we expect a pull request with benchmarks from you?

[alisher-matkurbanov]

@cclauss well, I try!
I just need to compare 2 versions and include this benchmarks in pr message with new version if it better, huh?

[cclauss]

That would be perfect. https://docs.python.org/3/library/timeit.html might be helpful in this exercise.

[alisher-matkurbanov]

@cclauss Hello! Sorry for long response. I tried to implement canonical version of this algorithm without recomputing hash for all string, but my implementation was 1.5 - 2 times slower than simple implementation that is here. So, I think we may close this issue.

[cclauss]

Cool. Always good to have a few benchmarks to test our intuitions.
Premature optimization is a consistent problem for algorithm builders.

[alisher-matkurbanov]

@cclauss Oh, and I see someone already replaced old solution to new solution that is the same as I mentioned here.