Crivello di Eratostene in Haskell

Question

sto risolvendo alcuni problemi classici a Haskell per sviluppare le mie capacità e funzionali ho un problema di realizzare un'ottimizzazione suggerito a http://programmingpraxis.com/2009/02/19/sieve-of-eratosthenes/

ho tre "soluzioni" a questo problema e la il terzo è troppo lento rispetto alla seconda soluzione. Qualcuno può suggerire alcuni miglioramenti al mio codice ?

miei implementazioni sono qui: http://hpaste.org/40261/sieve_of_eratosthenes

Answer 1

Mi sembra il problema con la terza revisione è come si sceglie il prossimo elemento da vagliare. Incremento indiscriminato di 2. Il problema è che si setaccia su numeri non necessari. Per esempio, in questa versione, alla fine passerai 9 come m, e stai andando a fare una ricorsione extra per filtrare su 9, anche se non è nemmeno nella lista, e quindi non avresti dovuto sceglierlo in primo luogo (dal momento che sarebbe stato rimosso nel primo filtro su 3)

Anche se la seconda versione non avvia il filtraggio oltre il quadrato del numero su cui si sposta, non sceglie mai un setacciamento non necessario valore.

In altre parole, penso che si finisca per setacciare ogni numero dispari tra 3 e n. Invece dovresti setacciare ogni numero dispari che non è stato già rimosso da un passaggio precedente.

Penso di implementare correttamente l'ottimizzazione dell'avvio del setaccio sul quadrato del valore di vaglio corrente, devi mantenere il fronte dell'elenco mentre setacciare sul retro dove il retro contiene gli elementi> = il quadrato della vagliatura valore. Penso che questo ti costringerebbe ad usare concatenazioni, e non sono così sicuro che l'ottimizzazione sia abbastanza buona da annullare il sovraccarico indotto dall'uso di ++.

Answer 2

Prima di tutto, mod è lento in modo da utilizzare rem in situazioni in cui non importa (quando non si tratta di aspetti negativi, in fondo). In secondo luogo, utilizzare Criterion per mostrare (a se stessi) ciò che è più veloce e quali cambiamenti sono in realtà le ottimizzazioni. So che non sto dando una risposta completa per mettere in discussione con questo, ma è un buon posto per voi (e altri answerers potenziali) di avviare, quindi ecco qualche codice:

import List 
import Criterion.Main 

main = do 
    str <- getLine 
    let run f = length . f 
     input = read str :: Integer 
    defaultMain [ bench "primes" (nf (run primes) input) 
       , bench "primes'" (nf (run primes') input) 
       , bench "primes''" (nf (run primes'') input) 
       , bench "primesTMD" (nf (run primesTMD) input) 
       , bench "primes'TMD" (nf (run primes'TMD) input) 
       , bench "primes''TMD" (nf (run primes''TMD) input) 
       ] 
    putStrLn . show . length . primes'' $ (read str :: Integer) 

-- primeira implementação 
primes n 
    | n < 2 = [] 
    | n == 2 = [2] 
    | n `mod` 2 == 0 = primes' 
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then 
         n:primes' 
        else 
         primes' 
    where primes' = primes (n - 1) 

primesTMD n 
    | n < 2 = [] 
    | n == 2 = [2] 
    | n `mod` 2 == 0 = primes' 
    | otherwise = if (find (\x -> n `rem` x == 0) primes') == Nothing then 
         n:primes' 
        else 
         primes' 
    where primes' = primesTMD (n - 1) 

-- segunda implementação 
primes' :: Integer -> [Integer] 
primes' n = sieve $ 2 : [3,5..n] 
    where sieve :: [Integer] -> [Integer] 
      sieve [] = [] 
      sieve l@(x:xs) 
       | x*x >= n = l 
       | otherwise = x : sieve list' 
       where list' = filter (\y -> y `mod` x /= 0) xs 

primes'TMD :: Integer -> [Integer] 
primes'TMD n = sieve $ 2 : [3,5..n] 
    where sieve :: [Integer] -> [Integer] 
      sieve [] = [] 
      sieve l@(x:xs) 
       | x*x >= n = l 
       | otherwise = x : sieve list' 
       where list' = filter (\y -> y `rem` x /= 0) xs 

-- terceira implementação 
primes'' :: Integer -> [Integer] 
primes'' n = 2 : sieve 3 [3,5..n] 
    where sieve :: Integer -> [Integer] -> [Integer] 
      sieve _ [] = [] 
      sieve m l@(x:xs) 
       | m*m >= n = l 
       | x < m*m = x : sieve m xs 
       | otherwise = sieve (m + 2) list' 
       where list'= filter (\y -> y `mod` m /= 0) l 

primes''TMD :: Integer -> [Integer] 
primes''TMD n = 2 : sieve 3 [3,5..n] 
    where sieve :: Integer -> [Integer] -> [Integer] 
      sieve _ [] = [] 
      sieve m l@(x:xs) 
       | m*m >= n = l 
       | x < m*m = x : sieve m xs 
       | otherwise = sieve (m + 2) list' 
       where list'= filter (\y -> y `rem` m /= 0) l 

Avviso la migliore esecuzione del varianti usando rem:

$ ghc --make -O2 sieve.hs 
$./sieve 
5000 
... 
benchmarking primes 
mean: 23.88546 ms, lb 23.84035 ms, ub 23.95000 ms 

benchmarking primes' 
mean: 775.9981 us, lb 775.4639 us, ub 776.7081 us 

benchmarking primes'' 
mean: 837.7901 us, lb 836.7824 us, ub 839.0260 us 

benchmarking primesTMD 
mean: 16.15421 ms, lb 16.11955 ms, ub 16.19202 ms 

benchmarking primes'TMD 
mean: 568.9857 us, lb 568.5819 us, ub 569.4641 us 

benchmarking primes''TMD 
mean: 642.5665 us, lb 642.0495 us, ub 643.4105 us 

Mentre vedo che si sta facendo questo per il tuo formazione, la sua pena di notare i link correlati di Primes on Haskell.org e il digiuno Primes package su hackage.