Re: Find index of maximal element in multi-dimensional array
- To: mathgroup at smc.vnet.net
- Subject: [mg73582] Re: Find index of maximal element in multi-dimensional array
- From: Ray Koopman <koopman at sfu.ca>
- Date: Thu, 22 Feb 2007 04:36:20 -0500 (EST)
- Reply-to: koopman at sfu.ca
There are n^2 elements in z, so it shouldn't be too surprising that the upper curve looks quadratic. Try the following: << Graphics`Graphics` e1 = Compile[{{z, _Real, 1}}, Max[z] ]; e2 = Compile[{{z, _Real, 1}}, Position[z, Max[z]]]; e3 = Compile[{{z, _Real, 1}}, Ordering[z, -1] ]; res1 = res2 = res3 = {}; z =.; Do[ z = Table[Random[], {n}]; res3 = { res3, Timing[ e3[z]; ][[1, 1]] }; res2 = { res2, Timing[ e2[z]; ][[1, 1]] }; res1 = { res1, Timing[ e1[z]; ][[1, 1]] }; z =.; , {n, 1, 4000001, 1000000 } ]; DisplayTogether[ { ListPlot[ Flatten[ res2 ], PlotJoined -> True, Frame->True, PlotStyle -> {Red, AbsoluteThickness[3]} ], ListPlot[ Flatten[ res1 ], PlotJoined -> True, PlotStyle -> {Green, AbsoluteThickness[3]} ], ListPlot[ Flatten[ res3 ], PlotJoined -> True, PlotStyle -> {Blue, AbsoluteThickness[3]} ] }]; Now the plots look almost linear, with the slope for Ordering being much smaller. One explanation would be that the kernel code for Ordering[_,-1] is simply more efficient than the code for Max. On Wed, 21 Feb 2007 11:51:02 +0100 (CET) ruebenko at uni-freiburg.de wrote: > > > Dear All, > > I was very impressed by Ray's answer. Ray used Ordering to solve the index > problem. Now, I thought that Ordering was of complexity O( n Log n). > Several other people including myself used Position and Max to get to the > solution. I'd expect that to be of complexity O( 2 n). But that is not the > case. > > << Graphics`Graphics` > f2 = Compile[{{z, _Real, 2}}, Position[#, Max[#]] &[Flatten@z]]; > f3 = Compile[{{z, _Real, 2}}, Ordering[Flatten@z, -1] ]; > res2 = res3 = {}; > z =.; > Do[ > z = Table[Random[], {n}, {n}]; > res3 = { res3, Timing[ f3[z]; ][[1, 1]] }; > res2 = { res2, Timing[ f2[z]; ][[1, 1]] }; > z =.; > , {n, 1, 2001, 500 } > ]; > DisplayTogether[ { > LogLinearListPlot[ Flatten[ res2 ], PlotJoined -> True, > PlotStyle -> Hue[1] ], > LogLinearListPlot[ Flatten[ res3 ], PlotJoined -> True, > PlotStyle -> Hue[0.65] ] > }] > > Can you help me understand this behaviour? Thanks in advance. > > Oliver > > On Wed, 21 Feb 2007, Ray Koopman wrote: > >> On Feb 20, 3:17 am, "Andrew Moylan" <andrew.j.moy... at gmail.com> wrote: >>> Hi all, >>> >>> Here's a two-dimensional array of numbers: >>> >>> z = Table[Random[], {5}, {6}] >>> >>> What's an efficient way of finding the index of the maximal element of >>> z? Here's one way: >>> >>> Last[Sort[Flatten[MapIndexed[{#2, #1} & , z, {2}], 1], >>> OrderedQ[{#1[[2]], #2[[2]]}] & ]] >>> >>> The output is like this: >>> >>> {{5, 4}, 0.921344} >>> >>> But it's so untidy. Any better ideas? >>> >>> Cheers, >>> >>> Andrew >> >> z = Table[Random[],{5},{n = 6}] >> >> {{0.247831, 0.85266, 0.87098, 0.840725, 0.808299, 0.160707}, >> {0.692361, 0.613514,0.758175, 0.823928, 0.0331389,0.330202}, >> {0.155955, 0.89171, 0.770831, 0.327228, 0.974979, 0.25434}, >> {0.325965, 0.5732, 0.388035, 0.0842301,0.089699, 0.99669}, >> {0.140205, 0.23157, 0.218719, 0.155965, 0.331906, 0.0708631}} >> >> {Ceiling[#/n],Mod[#,n,1]}&@@Ordering[Flatten@z,-1] >> >> {4,6} >> > > Oliver Ruebenkoenig, <ruebenko AT uni-freiburg.de> >