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

[Henrik Christian Grove <sslug@sslug>]

Ole Tange <sslug@sslug> writes:

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

Jeg er teoretiker og jeg forudsiger ikke køretider, men beskriver kun den
symptotiske udvikling.

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

Nu har jeg ikke lige tid til at læse de slides igennem [1], men det princip du
nævner er jeg bekendt med, men det er svært at tage højde for den slags, når
man vil udtale sig teoretisk om tingene. [2]

I det konkrete tilfælde er det sandsynligvis også lige meget. Det forslag jeg
kritiserede gennemlæste hele datasættet, og ville derfor i de fleste tilfælde
generere mindst lige så mange sidefejl som mit forslag der kun undersøger en
brøkdel af datasættet. 
Selv hvis datasættet er enormt, kan mit forslag højst [3] generere O(log n)
sidefejl (en pr. tal der skal læses). Det kritiserede forslag kan ikke undgå
at fremkalde O(n) sidefejl (svarende til antallet af sider der er brugt til
tabellen, hvilket må antages at være lineært i antallet af tal).
Hvis datasættet endelig bliver så enormt at sidefejl bliver en reel bekymring
skulle man nok snarere overveje anvendelsen af split, for som jeg gjorde
opmærksom på, vil den til enhver tid dominere køretiden. 
Min primære pointe var faktisk at tallene var sorteret, og at det var dumt
ikke at gøre brug af dette. Min lidt mere skjulte pointe var at opfordre
spørgeren til ikke blot at skrive det færdige forslag af, men i stedet tænke
sig om, og selv skrive noget kode.

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

Tjaa...

Henrik

[1] Og et kig på de quizzer du henviser til, gør mig ikke meget klogere. (De
to kodestumper i den ene, er så vidt jeg kan se ikke ækvivalente, og i den
anden, synes jeg det bliver sværere for oversætteren.)

[2] Sålænge vi diskuterer aymptotiske køretider, tvivler jeg også på at det
giver en forskel. Hvis vi bare antager at adgangstiden til det primære lager
(hvad enten det er cachen, ram'men eller disken) er konstant, er det nemlig
aymptotisk ligegyldigt hvor lang tid det tager.

[3] Men det kommer muligvis tæt på, når datasættet er så stort som vi her
taler om.



-- 
Henrik Grove --- sslug@sslug --- http://www.diku.dk/students/grove/
----------------------------------------------------------------------
Linux overalt! - og det kan kun gå for langsomt!