4 ms·

Good article. I've implemented Boyer-Moore several times and it's ridiculously fast on typical English text, especially with long search strings. I haven't imp

• 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 ago
    That’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 ago
      To 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.