4 ms·
KMP is so slow, it's not worth it. https://rurban.github.io/smart/results/all/englishTexts.html https://rurban.github.io/smart/results/all/englishTexts.html BM
by rurban 3y ago
KMP is so slow, it's not worth it. https://rurban.github.io/smart/results/all/englishTexts.html https://rurban.github.io/smart/results/all/englishTexts.html
BM beats it easily, not talking about the best two-way search algorithms, as implemented in musl.
Usually Thierry Lecroqs site has all the graphical descriptions of string search algos, just the latest are missing. https://www-igm.univ-mlv.fr/~lecroq/string/index.html https://www-igm.univ-mlv.fr/~lecroq/string/index.html
- klabb3 3y agoThat’s funny. I remember the wake up after doing all the complexity analysis and such of academia, that once you’re engineering for performance, it’s often very different from theory. For instance, a lot of heap-allocations and the resulting memory fragmentation can really tank performance on real hardware. Naive linked lists for instance, is a good example of something that looks super useful in CS class, but turns out is quite niche in practice, and also quite differently implemented.
- taeric 3y agoTo be fair, it is largely the Big O analysis that is very different. And that is easily understood as a case of Goodhart's Law. It remains a good way of comparing the growth of algorithms, of course; but a full analysis would include more than only the top end growth numbers.