Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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
share|improve this answer
    
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! –  rasher Mar 19 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 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... –  rasher Mar 20 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 at 6:27
1  
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... –  rasher Mar 22 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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.