MathGroup Archive 1998

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

Search the Archive

Re: Find Max of "Concave" List

  • To: mathgroup at smc.vnet.net
  • Subject: [mg13200] Re: Find Max of "Concave" List
  • From: "Allan Hayes" <hay at haystack.demon.cc.uk>
  • Date: Mon, 13 Jul 1998 07:42:48 -0400
  • References: <6n4rki$o17@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Jrgen Tischer wrote in message <6n4rki$o17 at smc.vnet.net>...
>Hi Chris,
>not elegant, but quite fast: bisection:
>
>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]]]]
>
>J=FCrgen

Jrgen,
Reducing the amount of testing at each step might be a good overall
strategy:

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

concaveMax2[li_]:=
Module[{a=1,b=Length[li],n},
     While[a!=b,
        n=Quotient[b+a,2];
        If[li[[n]]<li[[n+1]],a=n+1,b=n]

     ];
     li[[a]]
]

TEST:
li = Join[ Range[10000],Reverse[Range[9000]]];

concaveMax[li]
10000

concaveMax2[li]
10000

Do[concaveMax[li],{100}]//Timing
{1.05 Second,Null}

Do[concaveMax2[li],{100}]//Timing
{0.66 Second,Null}

Allan

------------------------------------------------------------- Allan
Hayes
Training and Consulting
Leicester UK
http://www.haystack.demon.co.uk
hay at haystack.demon.co.uk
voice: +44 (0)116 271 4198
fax: +44(0)116 271 8642


>
>-----Original Message-----
>From: Chris Farr <farr at brown.edu>
To: mathgroup at smc.vnet.net
>Subject: [mg13200] [mg12918] Find Max of "Concave" List
>
>
>>
>>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: symbolized symbol in LHS of function
  • Next by Date: Anyone use MultiplierMethod.m Package for Nonlinear Optimization?
  • Previous by thread: symbolized symbol in LHS of function
  • Next by thread: Anyone use MultiplierMethod.m Package for Nonlinear Optimization?