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