Rotate each row of the cross product by n steps where n is the row number
q)(til n:count b) rotate' a=/:b
000000000000010000000000b
000000000000010000000000b
000000000000010000001000b
000000001000010000001000b
Perform AND reduction along the columns to find the full matches.
q)(&/) (til n:count b) rotate' a=/:b
000000000000010000000000b
And there we have it. A naive string search in an array language.
Now some interesting advantages fall out of rediscovering this:
- It's obviously parallelisable: The "obvious" (iterative) solution in other languages isn't, and without some difficulty it isn't clear where the work can be split up.
- It uses "outer product" with compare = instead of multiplication × -- an experienced programmer might forget how deeply satisfying it is when first learning how to compose operators
- With some thought it gives a programmer ideas on how they can do string search even faster. Fast string search in an iterative language doesn't look anything like the naive solution.
b⍷a (b find-in a) is useful enough that an experienced programmer should expect a "modern" language to implement it (in q it's called "ss", other languages of course call it different things) but it is far from necessary, and we might cheat ourselves of something. After all, when we are experienced enough to see these things as obvious, other things become obvious as well.
It's extremely intuitive!
Let me illustrate why with q: Form a cross product of text with the substring, testing for equality of each character Rotate each row of the cross product by n steps where n is the row number Perform AND reduction along the columns to find the full matches. And there we have it. A naive string search in an array language.Now some interesting advantages fall out of rediscovering this:
- It's obviously parallelisable: The "obvious" (iterative) solution in other languages isn't, and without some difficulty it isn't clear where the work can be split up.
- It uses "outer product" with compare = instead of multiplication × -- an experienced programmer might forget how deeply satisfying it is when first learning how to compose operators
- With some thought it gives a programmer ideas on how they can do string search even faster. Fast string search in an iterative language doesn't look anything like the naive solution.
b⍷a (b find-in a) is useful enough that an experienced programmer should expect a "modern" language to implement it (in q it's called "ss", other languages of course call it different things) but it is far from necessary, and we might cheat ourselves of something. After all, when we are experienced enough to see these things as obvious, other things become obvious as well.