search

tokiwa-software / fuzion

The Fuzion Language Implementation
https://fuzion-lang.dev
GNU General Public License v3.0
46 stars 11 forks source link

Optimized `Sequence.find` using Knuth-Morris-Pratt algorithm #3711

Closed fridis closed 3 days ago

fridis commented 1 week ago

Currently, our implementation of Sequence.find may end up requiring quadratic runtime. We should use the KMP Algorithm, a racket version is presented here. A test case that requires quadratic time is ("a"*2*n).find "a"*n+"b".

michaellilltokiwa commented 1 week ago

Other algorithms that do not have quadratic complexity include Boyer-Moore: https://stackoverflow.com/questions/56418773/when-is-rabin-karp-more-effective-than-kmp-or-boyer-moore https://www.cs.utexas.edu/~moore/publications/sustik-moore.pdf

Boyer-Moore seems to offer predictable performance as well.