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