# Values (or positions) of array row elements within a specified number of positions from target value

I have the need to collect values from the rows of rectangular arrays of arbitrary precision integers, given a target element value and allowed "distance" (positions +/- within the row from found targets).

E.g., given a target array of

ar={{6, 10, 6, 5, 7}, {10, 2, 2, 0, 7}, {0, 6, 3, 7, 5}, {2, 8, 6, 9, 1}, {8, 8, 5, 0, 8}}


and a target value of 5, with an allowed "distance" of 2, the result should be

{10, 6, 5, 7, 3, 7, 5, 8, 8, 5, 0, 8}


Result must be order-preserving, i.e., as if the array were "read" left to right, top to bottom.

I'm using this:

nearEles[array_, ele_, dist_, posOnly_: False] :=
With[{r = Range[-dist, dist], d = Dimensions[array][[2]]},
If[posOnly, #, Extract[array, #]] &[SparseArray[
Map[IntegerDigits[BitOr @@ (BitShiftLeft[FromDigits[#, 2], r]), 2, d] &,
SparseArray[BitXor[1, Unitize[array- ele]]]]]["NonzeroPositions"]]];


so in the above example, called as nearEles[ar,5,2] gets me what I need.

On actual data (typically 1K X 1K to 4K X 2K array size), performs pretty well.

Any ideas for a more efficient (and perhaps less ungainly) method?

-

It occurred to me that this problem can be recast as an image processing one. I think this approach is different enough to warrant its own answer. I like the style much better.

f3[array_List, ele_, dist_] :=
Image[array] ~Binarize~ {ele, ele} ~MaxFilter~ {0, dist} //
Join @@ Pick[array, ImageData @ #, 1] &

f3[ar, 5, 2]

{10, 6, 5, 7, 3, 7, 5, 8, 8, 5, 0, 8}


For best performance in version 7, before Pick was optimized, use "NonzeroPositions":

f3v7[array_List, ele_, dist_] :=
Image[array] ~Binarize~ {ele, ele} ~MaxFilter~ {0, dist} //
array ~Extract~ SparseArray[ImageData @ #]["NonzeroPositions"] &


This is faster than my f2 function from the other answer, especially with large distance values:

big = RandomInteger[{-9, 9}, {5000, 5000}];

(r2 = f2[big, 3, 8]) // Timing // First
(r3 = f3v7[big, 3, 8]) // Timing // First

r2 == r3

1.232

0.562

True

-
Ah, super clever! f3v7 wins in my tests (interesting that v7 needs Normal in your other solution, btw). +1 and accept, don't see this being bettered. Thanks as always! –  ciao Mar 19 '14 at 22:14
@rasher You're welcome. So f3v7 is faster than f3 even in version 9? Perhaps that is become of the need for Join in f3. –  Mr.Wizard Mar 20 '14 at 5:55
Yep, not hugely, but consistently. Even stranger, I'd tried methods using both MaxFilter and Dilation on straight arrays. Dilation is vastly faster when array is converted to image, operated, and converted back even though results are the same. Strange, must be some magic-sauce like it "knowing" about Unitize and optimizing. I fell a bit DOH giving up on it and assuming conversion would make it slower... –  ciao Mar 20 '14 at 6:18
@rasher For some reason I forget about MaxFilter. I just tried it and it's as fast as Dilation on an Image. I think I'll update my answer to use it since it's somewhat cleaner. As to why the filters are faster on Image I'll do some investigating, but I know that the Image format has changed since v7. (I believe it is now atomic, i.e. AtomQ yields true?) –  Mr.Wizard Mar 20 '14 at 6:27
Oops - happened to glance a timings today, had order reversed, so above comment re: SA vs Pick is backward - it is Pick (at least on v9) that had the consistent advantage. Sorry about misleading boo-boo... –  ciao Mar 22 '14 at 6:50

I got an error running your code in version 7 and I had to use FromDigits[Normal@#, 2] to fix it. Therefore I don't know if my comparative timings are meaningful but here is what I came up with:

f2[array_, ele_, dist_] :=
SparseArray[Unitize[array - ele], Automatic, 1]["AdjacencyLists"] //
Outer[Plus, Range[-dist, dist], #, 1] & //
Clip[Join ~MapThread~ #, {1, Length @ First @ array}] & //
Join @@ MapThread[Part, {array, Union /@ #}] &


This runs twice as fast as your (modified) code on my machine:

big = RandomInteger[{-9, 9}, {3500, 3500}];

(r1 = nearEles[big, 7, 2]) // Timing // First
(r2 = f2[big, 7, 2])       // Timing // First

r1 == r2

0.483

0.234

True

-