       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)

```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} ],
>>     ListPlot[ Flatten[ res1 ], PlotJoined -> True,
>>       PlotStyle -> {Green, AbsoluteThickness} ],
>>     ListPlot[ Flatten[ res3 ], PlotJoined -> True,
>>       PlotStyle -> {Blue, AbsoluteThickness} ]
>>     }];
>>
>> 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/ArcCsch 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