Re: SV: [PERL] string med numre > given væ rdi

[Ole Tange <sslug@sslug>]

On 6 Jul 2000, Henrik Christian Grove wrote:

> Jørgen Altmann <sslug@sslug> writes:
> 
> > Hej Peter
> > 
> > Dette er èn af de mange løsningsforslag:
> > 	  
> > 	  $test  = -3;
> > 	  $antal =  0;
> > 	  @str = split(' ',$str);
> > 	  foreach(@str){ $antal += ($_ > $test) };
> 
> Det var dog et umådeligt langsomt[1] forslag. Når man ved listen er sorteret
:
> [1] Okay, vi kan godt blive enige om at split sikrer at køretiden altid bliver
> O(n), og at vi næppe kan undgå et split (med mindre vi får ekstremt mange
> oplysninger om tallene). Men det skal altså ikke være nogen grund til at vælge
> en O(n) løsning for resten af opgaven, når det nu kan gøres i O(log n).

Ikke for at kritisere dit indlæg, men verden, hvor man kunne forudsige
køretider har ændret sig en del.

http://www.fftw.org/fftw-slides.ps.gz har et par eksempler på dette (side
33ff): Nogle gange kan det bedre betale sig at udføre en hel masse
instruktioner, hvis blot man kan slipper for at accesse memory, der er
"langt væk".

Faktisk synes jeg princippet i fftw er ret frækt: Optimering til lige
bestemt _din_ maskine ved runtime!


/Ole
-- 
Du må ikke spamme.
   -- Frit efter Markedsføringsloven §6a
      http://www.fs.dk/jura/loveregl/mfl/l_mfl.htm