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


  • Prev by Date: Re: Diferent solution of integral in versions 4 and 5...
  • Next by Date: Re: ReplaceList and //.
  • Previous by thread: Re: Find index of maximal element in multi-dimensional array
  • Next by thread: Re: Find index of maximal element in multi-dimensional array