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

Question

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?

Answer 1

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

Answer 2

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