Stile Haskell/efficienza

Question

Quindi stavo lavorando a un modo per generare pigramente i primi, e ho trovato queste tre definizioni, che funzionano tutte in modo equivalente - solo controllando se ogni nuovo intero ha un fattore tra tutti i precedenti numeri primi:

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 

così sembra a me primes2 dovrebbero essere un po 'più veloce di primes1, in quanto evita ricalcolare f_ = f (const True) per ogni intero (che io che richiede un lavoro su ordine del numero di numeri primi che abbiamo 'ho trovato finora), e lo aggiorna solo quando enc cacciare un nuovo primo.

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

devo prendere una lezione da questo, e supponiamo che se posso rappresentare una funzione come un'operazione su una matrice, che io implementarlo nel secondo modo di efficienza, o c'è qualcosa che accende qui ?

Answer 1

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

---

Comunque, tornando alla domanda. A volte utilizzare le funzioni come strutture dati è la migliore rappresentazione per un determinato compito, e talvolta no. I "migliori" in termini di facilità di codifica e "migliori" in termini di prestazioni non sono sempre la stessa cosa. La tecnica "funziona come strutture di dati" è essenziale per runtime compilation, ma come quella pagina avverte,

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

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.

---

di spremere cicli di setaccio primo infinita, sbarazzarsi delle chiamate per mod! La moltiplicazione, la divisione e il modulo intero sono molto più lenti dell'aggiunta e della sottrazione di interi. Sulla mia macchina, questa implementazione si avvicina al 40% più velocemente quando si calcolano i 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 oltre.

Answer 2

Si noti che primes3 può essere reso più efficiente modificando ps++[x] a (x:ps).L'esecuzione di (++) è lineare nella lunghezza del suo argomento di sinistra, ma costante nella lunghezza dell'argomento di destra.