12 ms·

Interesting. You may be interested in a more modern search algorithm to replace Boyer Moore. I recently presented HashChain, a very fast sublinear search algo

Interesting. You may be interested in a more modern search algorithm to replace Boyer Moore. I recently presented HashChain, a very fast sublinear search algorithm at the Symposium of Experimental Algorithms. https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea2024/LIPIcs.SEA.2024.24/LIPIcs.SEA.2024.24.pdf https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea... It's the fastest sublinear search algorithm around in almost all cases. I also have a guaranteed worst-case linear version (which is still sublinear and much faster than Boyer Moore in the average case). Sample code is available here: https://github.com/nishihatapalmer/HashChain https://github.com/nishihatapalmer/HashChain If you're interested, let me know.

rurban 2y ago
A benchmark of all good string-search algos is here: https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/ The ones parent picked are not amongst the best at all. I added a ticket to add your HashChain algos to be tested also. Preliminary testing shows indeed excellent numbers for hc2-hc4. Comes close to musl
- MattPalmer1086 2y ago
  Amazing, thanks. The sample code is already written to integrate with smart (I have also contributed to the smart tool!). You may want to add the linear version of HashChain too (in the same GitHub repo).
- MattPalmer1086 2y ago
  Looks like musl is using pointer arithmetic? Can speed up most of the algorithms in smart by using that. It's faster than using array indexing generally. I didn't do that in the sample code for HashChain simply because it would be an unfair comparison with the others.
- MattPalmer1086 2y ago
  The musl timings are actually incorrect, because it resets the timer on each iteration of the main loop used to count matches. So you only record the time to make the last match, not the total time. I've raised an issue on the GitHub for smart.
  - rurban 2y ago
    Oh, oh, thanks!
    - MattPalmer1086 2y ago
      I was surprised that an algorithm from 1991 was the fastest! My first rule of benchmarking is to be suspicious of surprises!
      - rurban 2y ago
        Yes, I updated the benchmarks of the best string search algos.

rurban 2y ago

A benchmark of all good string-search algos is here: https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/ The ones parent picked are not amongst the best at all. I added a ticket to add your HashChain algos to be tested also. Preliminary testing shows indeed excellent numbers for hc2-hc4. Comes close to musl

MattPalmer1086 2y ago
Amazing, thanks. The sample code is already written to integrate with smart (I have also contributed to the smart tool!). You may want to add the linear version of HashChain too (in the same GitHub repo).
MattPalmer1086 2y ago
Looks like musl is using pointer arithmetic? Can speed up most of the algorithms in smart by using that. It's faster than using array indexing generally. I didn't do that in the sample code for HashChain simply because it would be an unfair comparison with the others.
MattPalmer1086 2y ago
The musl timings are actually incorrect, because it resets the timer on each iteration of the main loop used to count matches. So you only record the time to make the last match, not the total time. I've raised an issue on the GitHub for smart.
- rurban 2y ago
  Oh, oh, thanks!
  - MattPalmer1086 2y ago
    I was surprised that an algorithm from 1991 was the fastest! My first rule of benchmarking is to be suspicious of surprises!
    - rurban 2y ago
      Yes, I updated the benchmarks of the best string search algos.