stile Haskell / efficienza

Question

Quindi stavo lavorando su un modo per generare numeri primi pigramente, e mi si avvicinò con queste tre definizioni, che tutto il lavoro in modo equivalente - basta verificare se ogni nuovo intero ha un fattore tra tutti i numeri primi precedenti:

primes1 :: [Integer]
primes1 = mkPrimes id [2..]
  where mkPrimes f (x:xs) = 
          if f (const True) x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) xs
          else
            mkPrimes f xs

primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
  where mkPrimes f f_ (x:xs) = 
          if f_ x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) ( f $ g $ const True) xs
          else
            mkPrimes f f_ xs

primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
  where mkPrimes ps (x:xs) = 
          if all (\p -> x `mod` p > 0) ps
          then 
            x : mkPrimes (ps ++ [x]) xs
          else
            mkPrimes ps xs

Quindi, mi sembra primes2 dovrebbe essere un po 'più veloce di primes1, in quanto evita ricalcolo f_ = f (const True) per ogni intero (che I pensare richiede un lavoro su ordine del numero di numeri primi che abbiamo trovato finora), e aggiornamenti solo quando ci imbattiamo in un nuovo primo.

Proprio da prove non scientifiche (in esecuzione take 1000 in ghci) sembra primes3 corre più veloce di primes2.

Devo prendere una lezione da questo, e assumere che se posso rappresentare una funzione come un'operazione su una matrice, che io implementarlo nel secondo modo per efficienza, o c'è qualcosa altra cosa sta succedendo qui?

Answer 1

Qual è il secondo argomento della f del necessario per? A mio parere, entrambe queste alternative sono più leggibili, e non influenzano in modo significativo le prestazioni ...

...
            let g y = f y && y `mod` x > 0 in
            x : mkPrimes g xs
...

import Control.Arrow  -- instance Monad (-> r)
import Control.Monad  -- liftM2
(.&&.) = liftM2 (&&)
...
            let g y = y `mod` x > 0 in
            x : mkPrimes (f .&&. g) xs
...

---

In ogni caso, tornando alla domanda. A volte usando le funzioni come le strutture di dati è la rappresentazione migliore per un determinato compito, e qualche volta no. "Best", in termini di facilità di codifica e "migliore" in termini di prestazioni non sono sempre la stessa cosa. La tecnica "funziona come strutture di dati" è essenziale per runtime compilazione , ma come quella pagina avverte,

  

compilazione runtime a volte si può vincere significativi guadagni di efficienza, ma spesso può vincere quasi nulla al costo del vostro aumento dello stress e la riduzione della produttività.

Nel tuo caso, è probabile che il sovraccarico di costruire ogni f :: Integer -> ... -> Bool è significativamente superiore al sovraccarico di costruire ogni ps :: [Integer], con poca o nessuna differenza quando si chiama f ... x contro all ... ps.

---

Per spremere cicli di setaccio primo infinita, sbarazzarsi delle chiamate per mod! Intero moltiplicazione, divisione e modulo sono molto più lenti intero addizione e sottrazione. Sulla mia macchina, questa implementazione orologi a 40% più veloce nel calcolo dei primi 1000 numeri primi (GHC 6.10.3 -O2).

import qualified Data.Map as M
primes' :: [Integer]
primes' = mkPrimes 2 M.empty
  where
    mkPrimes n m = case (M.null m, M.findMin m) of
        (False, (n', skips)) | n == n' ->
            mkPrimes (succ n) (addSkips n (M.deleteMin m) skips)
        _ -> n : mkPrimes (succ n) (addSkip n m n)
    addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m
    addSkips = foldl' . addSkip

In azione (con un po 'di sintassi JSON-ish),

   mkPrimes 2 {}
=> 2 : mkPrimes 3 {4: [2]}
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]}
=> 2 : 3 : mkPrimes 5 {6: [2, 3]}
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]}
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]}
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]}
...

la mappa tiene traccia dei multipli futuri, utilizzando nient'altro da aggiungere.

Answer 2

Si noti che primes3 può essere resa più efficiente modificando ps++[x] a (x:ps). Il (++) esecuzione è lineare nella lunghezza della sua tesi di sinistra, ma costante nella lunghezza dell'argomento a destra.