Using Extract where some indices are out of bounds (efficiently)
Julian Francis
How can I arrange to use Extract to extract values from an array; but
where some of the indices may be out of bounds, in which case they
should be simply ignored?
I wrote a simple arrayInBounds function, and then did a Select on that
to retrieve only the indices which are in bounds, which are then fed
into Extract. Whilst this works it seems to lead to a 150* reduction
in speed.
FYI:
My arrayInBounds function looks like this:
arrayInBounds[array_, index_] :=
If[index == {}, True,
First[index] > 0 && First[index] < Length[array] &&
arrayInBounds[array[[1]], Rest[index]]]
My support functions for the test are:
disks = Table[
Transpose[Position[DiskMatrix[r, 2*(r + 1) + 1], 1]], {r, 1, 30}];
positions[x_, y_, r_] := Transpose[{
disks[[r, 1]] + y - (r + 2),
disks[[r, 2]] + x - (r + 2)}]
My timing tests are:
In[291]:= Timing[lists=Table[Extract[image,Select[positions[x,y,
10],arrayInBounds[image,#]&]],
{y,11,64-11},
{x,11,64-11}];]
Out[291]= {17.175,Null}
In[292]:= Timing[lists2=Table[Extract[image,positions[x,y,10]],
{y,11,64-11},
{x,11,64-11}];]
Out[292]= {0.094,Null}
In[293]:= lists==lists2
Out[293]= True
image is assumed to be an array of at least 64*64.
In this particular case, the bounds are setup so that the checking
serves no purpose and can be eliminated, but I've only done this to
show the speed comparison with the no bounds checking comparison. The
speed difference is a factor of over 150! This seems surprising to me.
Is there a better way?
I don't think I can reformulate it using partitions, or the standard
imagefilter functions, because in general the functions positions will
be giving a complicated list of coordinates which doesn't naturally
fit into a square kernel.
Any help greatly appreciated.
Thanks,
Julian.
Ray Koopman
wrote:
Is this the sort of thing you're looking for?
myExtract[array_,indices_] := With[{m = Dimensions@array}, Extract[
array, Select[indices, And@@Positive@# && And@@Thread[# <= m]&]]]
a = Array[FromDigits@{##}&,{2,3,4}]
{{{111,112,113,114},{121,122,123,124},{131,132,133,134}},
{{211,212,213,214},{221,222,223,224},{231,232,233,234}}}
myExtract[a,{{0,1,2},{1,2,3},{2,3,4},{3,4,5}}]
{123,234}
myExtract[a[[2,2]],Transpose@{Range[0,5]}]
{221,222,223,224}
Ray Koopman
If the array from which you are extracting elements is two-dimensional
and square then this will be much faster than my previous suggestion:
myExtract2[array_,indices_] := With[{m = Length@array},
Extract[array, Part[indices,
SparseArray[Times@@UnitStep[(#-1)*(m-#)&@Transpose@indices]] /.
SparseArray[_,_,_,d_] :> Flatten@d[[2,2]] ]]]
Ray Koopman
To remove the restriction on myExtract2 to two-dimensional square
arrays, just change Length@array to Dimensions@array. This will make
it as general as myExtract, without slowing it for two-dimensional
square arrays.
Julian Francis
> On Jan 5, 11:01 pm, Ray Koopman <koop...@sfu.ca> wrote:
>
>
>
>
>
>
>
>
>
> > On Jan 4, 1:28 am, Ray Koopman <koop...@sfu.ca> wrote:
> >> wrote:
> >>> Dear all,
>
> >>> How can I arrange to use Extract to extract values from an array;
> >>> but where some of the indices may be out of bounds, in which case
> >>> they should be simply ignored?
>
> >>> I wrote a simple arrayInBounds function, and then did a Select on
> >>> that to retrieve only the indices which are in bounds, which are
> >>> then fed into Extract. Whilst this works it seems to lead to a
> >>> 150* reduction in speed.
>
> >>> FYI:
> >>> My arrayInBounds function looks like this:
>
> >>> arrayInBounds[array_, index_] :=
> >>> If[index == {}, True,
> >>> First[index] > 0 && First[index] < Length[array] &&
> >>> arrayInBounds[array[[1]], Rest[index]]]
>
> >>> My support functions for the test are:
>
> >>> disks = Table[
[
> >> array, Select[indices, And@@Positive@# && And@@Thread[# <= m]&]]=
]
>
> >> a = Array[FromDigits@{##}&,{2,3,4}]
>
> >> {{{111,112,113,114},{121,122,123,124},{131,132,133,134}},
> >> {{211,212,213,214},{221,222,223,224},{231,232,233,234}}}
>
> >> myExtract[a,{{0,1,2},{1,2,3},{2,3,4},{3,4,5}}]
>
> >> {123,234}
>
> >> myExtract[a[[2,2]],Transpose@{Range[0,5]}]
>
> >> {221,222,223,224}
>
> > and square then this will be much faster than my previous suggestion:
>
> > myExtract2[array_,indices_] := With[{m = Length@array},
> > Extract[array, Part[indices,
> > SparseArray[Times@@UnitStep[(#-1)*(m-#)&@Transpose@indices]] /.
> > SparseArray[_,_,_,d_] :> Flatten@d[[2,2]] ]]]
>
> To remove the restriction on myExtract2 to two-dimensional square
> arrays, just change Length@array to Dimensions@array. This will make
> it as general as myExtract, without slowing it for two-dimensional
> square arrays.
Thank you very much; that is excellent. My timings indicates your
version is approximately 40 times faster than my original extract with
arrayInBounds version.
Thank you and kind regards,
Julian.
Ray Koopman
> [...]
> Thank you very much; that is excellent. My timings indicates your
> version is approximately 40 times faster than my original extract
> with arrayInBounds version.
Here's an improved version of myExtract2 that seems a little faster,
and a similar function, myExtract3, that may be faster still.
myExtract2[array_,indices_] := Extract[array, Part[indices,
SparseArray[Times@@UnitStep[(#-1)*(Dimensions@array-#)& @
Transpose@indices]] /. SparseArray[_,_,_,d_] :> Flatten@d[[2,2]] ]]
myExtract3[array_,indices_] := Extract[array, Part[indices,
SparseArray[Times@@MapThread[Clip[#1,{1,#2},{0,0}]&,
{Transpose@indices, Dimensions@array}]] /.
SparseArray[_,_,_,d_] :> Flatten@d[[2,2]] ]]