Re: Using Extract where some indices are out of bounds (efficiently)
- To: mathgroup at smc.vnet.net
- Subject: [mg115339] Re: Using Extract where some indices are out of bounds (efficiently)
- From: Julian Francis <julian.w.francis at gmail.com>
- Date: Sat, 8 Jan 2011 03:37:54 -0500 (EST)
- References: <iev2kf$4mq$1@smc.vnet.net> <ifup7d$cog$1@smc.vnet.net>
On Jan 7, 9:07 am, Ray Koopman <koop... at sfu.ca> wrote:
> On Jan 5, 11:01 pm, Ray Koopman <koop... at sfu.ca> wrote:
>
>
>
>
>
>
>
>
>
> > On Jan 4, 1:28 am, Ray Koopman <koop... at sfu.ca> wrote:
> >> On Dec 23 2010, 12:52 am, Julian Francis <julian.w.fran... at gmail.com>
> >> 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[
> >>> Transpose[Position[DiskMatrix[r, 2*(r + 1) + 1], 1]], {r, 1, 3=
0}];
>
> >>> 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.
>
> >> 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}
>
> > 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]] ]]]
>
> 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.