MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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>
> 


  • Prev by Date: Re: Showing that ArcSinh[2]/ArcCsch[2] is 3?
  • Next by Date: Re: Fuction definition
  • Previous by thread: Re: Find index of maximal element in multi-dimensional array
  • Next by thread: Re: obtaining an ordered subset of k elements