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