Sieve d'Eratosthène en Haskell

Question

Je résoudre certains problèmes classiques dans Haskell à développer ma fonctionnelle compétences et moi avons un problème à mettre en œuvre une optimisation proposée à ce « Programmation Praxis » le site :

J'ai trois solutions à ce problème et le troisième est trop lent par rapport à la seconde solution. Quelqu'un peut-il suggérer quelques améliorations mon code?

Mes mises en œuvre sont:

-- 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)

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

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

Answer 1

Me semble le problème avec votre troisième révision est la façon dont vous choisissez l'élément suivant pour passer au crible sur. Vous incrémenter sans discrimination par 2. Le problème est que vous avez ensuite passer au crible le nombre inutiles. par exemple, dans cette version votre finalement va passer 9 comme m, et vous allez faire une récursion supplémentaire pour filtre sur 9, même si elle est même pas dans la liste, et donc vous devriez avoir jamais pris en premier lieu (car il aurait été enlevé dans le premier filtre sur 3)

Même si la deuxième version ne démarre pas le filtrage devant le carré du nombre qu'il tamise sur, il ne choisit jamais une valeur de tamisage inutile.

En d'autres termes, je pense que vous finissez par tamiser sur chaque nombre impair entre 3 et n. Au lieu de cela, vous devriez tamiser sur chaque nombre impair qui n'a pas déjà été supprimé par un passage précédent.

Je pense à mettre en œuvre correctement l'optimisation du démarrage du tamis sur la place de la valeur EIPD actuelle, vous devez conserver le devant de la liste tout en tamisant sur le dos où dos contient les éléments> = le carré de la valeur EIPD . Je pense que cela vous oblige à utiliser concaténations, et je ne suis pas si sûr que l'optimisation est assez bon pour annuler la surcharge induite en utilisant ++.

Answer 2

Tout d'abord, mod est tellement lent utilisation rem dans des situations où il n'a pas d'importance (quand vous ne traitez pas avec des négatifs, essentiellement). En second lieu, l'utilisation Critère pour montrer (pour vous) ce qui est plus rapide et les changements sont en fait des optimisations. Je sais que je ne suis pas donner une réponse complète à vous la question avec cela, mais un bon endroit pour vous (et d'autres answerers potentiels) de commencer, donc voici un code:

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

Notez que le temps d'exécution améliorée des variantes en utilisant 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

Alors que je vois que vous faites cela pour votre propre éducation, la peine de noter les liens connexes de sur Haskell nombres premiers .org et rapide package sur hackage nombres premiers.