MathGroup Archive 1998

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

Search the Archive

Re: Find Max of "Concave" List


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


  • Prev by Date: Protection against some Front end problems and crashes
  • Next by Date: Re: Strange behavior of Sort
  • Previous by thread: Re: Find Max of "Concave" List
  • Next by thread: Re: Find Max of "Concave" List