Re: Max of Concave List...And The Winner Is....
- To: mathgroup at smc.vnet.net
- Subject: [mg13040] Re: [mg13016] Max of Concave List...And The Winner Is....
- From: Daniel Lichtblau <danl>
- Date: Sat, 4 Jul 1998 16:44:46 -0400
- References: <199806300426.AAA10249@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]]]]
Your conclusions are correct but should be examined with care.
Say your list has length n. Also suppose that the max is nowhere near
the middle (because this makes concaveMax trivial). Also let us work
with numericized lists because then it is typically faster to compare
elements.
The binary search code given is, like Max, O(n) in complexity. This is
because of use of Take. When finished, we will have formed sublists of
total length n. The fact that it is much faster than Max is simply due
to much smaller constant term. In our development version the Max
method is alot faster than before (by a constant factor) and can even
beat the binary search code. I use this version below.
binsearch[lst_] := Module[{i,x=lst},
(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])]
In[108]:= ll = Table[250*x+-(1/2)*x^2,{x,1,380000}];
In[109]:= lln = N[ll];
In[110]:= Timing[Max[lln]]
Out[110]= {0.22 Second, 31250.}
In[111]:= Timing[binsearch[lln]]
Out[111]= {0.38 Second, 31250.}
(You can try with other list lengths to show that the complexity is
O(n). Or just take my word for it).
Note that even when the max is near an end the bisection code is still
easily the fastest. As it should be, because the complexity is
O(log(n)).
In[113]:= Timing[concaveMax[lln]]
Out[113]= {0.01 Second, 31250.}
Daniel Lichtblau
Wolfram Research