Re: Effiziente Suche in geordneter Liste

[Oliver Ruebenkoenig <ruebenko@XXXXXXX.com>]

On Sun, 10 Jul 2011, Martin Heimann wrote:

> Liebe Kollegen,
>
> vorgegeben ist eine streng monoton aufsteigende Liste {x(1), x(2), ... 
> x(N)} reeller Zahlen.
>
> Wie finde ich am effizientesten die Indices ia und ib des Intervalls 
> {x(ia},x{ib}} in welchem ein gegebener Wert y liegt (d.h. 
> x(ia)<y<=x(ib))? Simples sequentielles Suchen mit Position etc. benötigt 
> Laufzeiten, welche proportional der Anzahl Elemente der Liste sind. Es 
> gibt jedoch Algorithmen, welche nur Laufzeiten proportional Log(N) 
> benötigen; in Mathematica habe ich jedoch nichts brauchbares gefunden. 
> Habe ich hier etwas übersehen oder kennt jemand einen bereits in 
> Mathematica programmierten Algorithmus der derart effizient ist?
>
> mit bestem Gruss
> Martin

Hallo Martin,

vielleicht so was in der Art:


mkSearch[in_] := Block[{data, mMax, nf},
  data = Sort[in];
  mMax = Length[data];
  nf = Nearest[data -> Automatic];
  With[{data = data, nf = nf, mMax = mMax},
   Function[s,
    Block[{n},
     {n} = nf[s];
     Switch[n,
      1, {1},
      mMax, {mMax},
      _, If[s <= data[[n]], {n - 1, n}, {n, n + 1}]]]]]]


test = RandomReal[{0, 1}, {10}]

f = mkSearch[test]

sData = RandomReal[{0, 1}, {10}]
AbsoluteTiming[f /@ sData ]

Hoffe das ist so was in der Richtung was Du suchst.

Gruss,
Oliver


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