Re: Find Max of "Concave" List
- To: mathgroup at smc.vnet.net
- Subject: [mg12959] Re: [mg12918] Find Max of "Concave" List
- From: Don Piele <piele at cs.uwp.edu>
- Date: Sun, 28 Jun 1998 02:51:49 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Chris, use binary search.
x =Join[y= Range[10000],Reverse[Range[9000]]];
Max[x]//Timing
{2.52 Second,10000}
(*Binary Search*)
(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])//Timing
{0.11 Second,10000}
Don Piele piele at cs.uwp.edu
University of Wisconsin - Parkside
-----------------------------------------
On Wed, 24 Jun 1998, Chris Farr wrote:
>
> I have a one-dimensional list which is concave. That is, if you did a
> ListPlot on the list you would have a concave curve.
>
> Given the concavity, when finding the max, it is inefficient to use
> Max[] which does a comparison on all elements of the list.
>
> Is there an elegant way to exploit the concavity when performing a
> Max[]? That is, the algorithm should stop when the next element in the
> list is lower then the previous element. This would limit the number
> of comparisons.
>
> Thanks,
>
> Chris Farr
>
>
>