Re: Find index of maximal element in multi-dimensional array

*To*: mathgroup at smc.vnet.net*Subject*: [mg73682] Re: Find index of maximal element in multi-dimensional array*From*: Ray Koopman <koopman at sfu.ca>*Date*: Sat, 24 Feb 2007 02:24:09 -0500 (EST)*Reply-to*: koopman at sfu.ca

The general function Ordering[z], with no second argument, should be O[n Log[n]], but Ordering[z,1] and Ordering[z,-1] are special cases that can be O[n] if the second argument is checked before starting. On Fri, 23 Feb 2007 16:26:30 +0100 (CET) ruebenko at uni-freiburg.de wrote: > > Thank you Ray, > > still i am surprised that the presumably O(n Log n) is faster than the > O(2n). > > Oliver > > On Wed, 21 Feb 2007, Ray Koopman wrote: > >> 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. >> > [...] > Oliver Ruebenkoenig, <ruebenko AT uni-freiburg.de> >