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

Max of Concave List...And The Winner Is....

• To: mathgroup at smc.vnet.net
• Subject: [mg13016] Max of Concave List...And The Winner Is....
• From: "Chris Farr" <farr at brown.edu>
• Date: Tue, 30 Jun 1998 00:26:13 -0400
• Sender: owner-wri-mathgroup at wolfram.com

Math Group:

Thanks for all of your help in finding the maximum of a list which is 
concave.  I tested the speed of 3 algorithms sent in on a list of
values  yielded by a quadratic function.  In short, in terms of speed,
"The  Bisection Method" won with "The Binary Search Method" coming in
a close  second.  Here is the list:

x = Table[40000*x+-(1/2)*x^2,{x,1,80000}];

The position of the list at the optimum is 40,000 (half way on the grid
 of 80,000).

Here is the list from slowest to fastest (the code for each algorithm is
 below)...

"Max[x]" ==>3.35 seconds
Catch-Throw Method" ==> 1.93 seconds "Binary Search Method" ==>
0.05 seconds "The Bisection Method" ==> 0. seconds


"Max[x]"

Max[x]

"Catch-Throw Method"

e=First[x];
Catch[Scan[If[#<e,Throw[e],e=#]&,Rest[x]]]

"Binary Search Method"

(While[Length[x]>1,i=Floor[Length[x]/2]; If[x[[i]]<=
x[[i+1]],x=Take[x,-Length[x]+i];,x=Take[x,i];]]; First[x])

"The Bisection Method"

concaveMax[li_]:= Module[{a=1,b=Length[li]}, While[b-a>1,
With[{n=Quotient[b+a,2]},
If[li[[n]]==li[[n+1]],Return[li[[n]]]];
If[li[[n]]<li[[n+1]],a=n+1,b=n]]]; Max[li[[a]],li[[b]]]]