in reply to Re^2: counting the number of 16384 pattern matches in a large DNA sequence
in thread counting the number of 16384 pattern matches in a large DNA sequence
Just as a matter of curiosity, have you ever come across a case in which there was a benefit from studying a string even once?
Yes. But it was
Boyer-Moore worked best in the days before the chip manufacturers had built string search algorithms into microcode; and before the advent of deeply pipelined architectures with branch predictions, when branching had a proportionally significantly greater impact on throughput than with modern hardware.
This allows the algorithm to trade intelligence for brute force.
With modern processors that overlap fetches and branching stalls with other parts of the opcodes, the benefits are greatly curtailed.
I tried to look up a old post of mine that benchmarked study having a beneficial effect, but couldn't find it.
I also tried to replicate my memory of what I was doing back then, but cannot reproduce it. Whether that's because my memory is bad, or my modern processor negates the benefits I'm not totally sure, but I suspect the latter.
|
|---|