Re: Max of Concave List...And The Winner Is....
- To: mathgroup at smc.vnet.net
- Subject: [mg13120] Re: Max of Concave List...And The Winner Is....
- From: Robert Knapp <rknapp>
- Date: Tue, 7 Jul 1998 03:44:23 -0400
- Organization: Wolfram Research, Inc.
- References: <6n9pf9$a2v@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Chris Farr wrote:
>
> 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]]]]
I will add some comments about the built in function Max. One reason
Max takes so long is that it does not know anything about the structure
of your list. Another more subtle reason Max takes so long is that in
version 3.0, it is optimized to find the maximum of a list of elements
which are numeric quantities (things like Sqrt[2], Pi), but are not
represented in the system.
In the current development version, we have developed better technology
for recognizing lists of numbers, so Max operates much faster than
before on a list of numbers:
In[1]:=
x = Table[40000*x+-(1/2)*x^2,{x,1,80000}]; Timing[Max[x]]
(Version 3.0.1) Out[1]= {5.76 Second, 800000000} (Development Version)
Out[1]= {0.29 Second, 800000000}
This is quite a bit faster. However, if your list consists entirely of
approximate machine numbers (or integers), the speed increase is even
greater:
In[2]:=
nx = Table[40000.*x+-.5*x^2,{x,1.,80000.}]; Timing[Max[nx]]
8 (Version 3.0.1) Out[2]=
{2.31 Second, 8. 10 }
8 (Development Version)
Out[2]= {0.01 Second, 8. 10 }
Rob Knapp
Wolfram Research, Inc.