Re: Effiziente Suche in geordneter Liste

[Martin Heimann <martin.heimann@XXXXXXX.de>]

Liebe Kollegen,

ausgezeichnet - vielen Dank!  Die Regula Falsi Version beschleunigt meine Anwendung immens. Die Variante von Udo ist 
zwar extrem elegant, hat jedoch Laufzeiten die linear mit der Anzahl Elemente der Liste ansteigen. 

Inzwischen habe ich gesehen, dass das Combinatorica Package die Funktion BinarySearch enthält, welche im wesentlichen 
mein Problem auch löst. Im Test verhält sich BinarySearch genau so schnell wie Die Regula Falsi Variante (vielleicht 
enthält ja BinarySearch den Regula Falsi Code...).

Viel Grüsse,
Martin



On Jul 11, 2011, at 19:06, Udo und Susanne Krause wrote:

> Hallo Martin, Markus & Oliver,
> 
>> hier ist eine einfache Implementation, die Log(n) Eigenschaften hat:
>> 
>> ListRegulaFalsi[data_List, q_] :=
>> FixedPoint[
>>  With[
>>    {middle = Ceiling[Mean[#]]},
>>    If[data[[middle]] < q, {middle, Last[#]}, {First[#], middle}]
>>    ] &,
>>  {1, Length[data]}
> 
> In[92]:= Timing[ListRegulaFalsi[Range[10^8], 63725.3]]
> Out[92]= {0.078, {63725, 63726}}
> 
> hier ist eine Funimplementation, die auch mit ungeordneten Listen funktioniert
> 
> In[88]:= Clear[heimannPosition]
> heimannPosition[l_?VectorQ, q_?NumericQ] := {0, 1} +
>   Plus @@ UnitStep[q - l];
> 
> In[93]:= Timing[heimannPosition[Range[10^8], 63725.3]]
> Out[93]= {13.619, {63725, 63726}}
> 
> sehr langsam natürlich, aber kaum Code; und hier ist die Schönschrift
> für die regula falsi, die somit auch kaum Code enthält:
> 
> In[121]:= Clear[ ListRF, m]
> ListRF[data_List, q_] :=
> FixedPoint[
>  Drop[{First[#], m = Ceiling[(Plus @@ #)/2], Last[#]},
>    If[data[[m]] < q, 1, -1]] &, {1, Length[data]}]
> 
> In[123]:= Timing[ListRF[Range[10^8], 63725.3]]
> Out[123]= {0.078, {63725, 63726}}
> 
> Gruss
> Udo.


----------------------------------------------------------------------------
Max-Planck-Institute for Biogeochemistry, PF 100164, D-07701 Jena, Germany 
Street Address:  Beutenberg Campus, Hans-Knoell-Straße 10, D-07745 Jena
Office: +49-3641-57-6350/6301
Mobile No:      +49-151-12035946
Home:   +49-3641-618247                    
Fax.:   +49-3641-57-7300
Skype:   mheimann
Email:   martin.heimann@XXXXXXX.de, 
              office.bgc-systems@XXXXXXX.de
Web:     http://www.bgc-jena.mpg.de/~martin.heimann