On Wed, Oct 12, 2011 at 1:49 PM, Marshall Lochbaum <mwlochb...@gmail.com> wrote: > J's E. implements Boyer-Moore, which makes it much faster than a standard > search. You could implement a standard search using sequential machines > (well, if you don't mind a transition table that grows with the size of the > label to find), but I'm fairly sure it's impossible to implement Boyer-Moore > using sequential machines, so your search would be several times slower and > probably not worth the advantage you get from stopping early.
The speedup of Boyer-Moore on machines with a modern cache architecture should not be measurable unless the label being looked for is longer than a cache line or unless the alternative algorithm is too bulky to fit in the instruction cache (which might be the case for sequential machine?) That said, to have sequential machine stop after finding 100 labels you would need (100 * label length) distinct states (and you would also need 1 + number of unique characters in label options at each state). Also, to get character position at state information out of sequential machine, you need to put it in trace mode (which gives you five integers for each character scanned). -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
