Re: Effiziente Suche in geordneter Liste

[Patrick Scheibe <patrick@XXXXXXX.de>]

Moin,

> (vielleicht enthält ja BinarySearch den Regula Falsi Code...).

Ja, es ist in dem Fall der gleiche Algorithmus. Wenn man die Vorschrift
aus dem "Sorting und Searching" von Gott Knuth direkt hinschreibt, dann
sieht's genauso aus, wie das was Markus gepostet hat.

Ich hatte nur kurz ueber Markus seine Antwort geschaut und wollte den
Binary Search mit gleicher Laufzeit als Alternative posten. Nachdem ichs
hingeschrieben hatte war ich dann etwas enttaeuscht, weils genauso
aussah wie Markus sein Schnipsel.. Da hab ichs wieder geloescht.

Cheers
Patrick

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