3 ms·
Oh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And
by dataflow 6y ago
Oh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And yeah I should really try out the max shift change, I came across it not too long ago but never got around to implementing it.
- MattPalmer1086 6y agoI find Horspool is almost always faster than Boyer Moore. For very short needles though (e.g. less than 8) it is hard to beat the SHIFT OR algorithm. Even though it is not sublinear, looking at every position, it tracks matches using a bitmask. In practice this is very fast and has very good cache hits. It easily beats BM or Horspool by quite a margin. They rely for speed in skips, and you don't get great skips with a short needle.