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