Style / efficacité Haskell

Question

Alors que je travaillais sur un moyen de générer des nombres premiers paresseusement, et je suis venu avec ces trois définitions, tous les travaux de manière équivalente - il suffit de vérifier si chaque nouvel entier a un facteur parmi tous les nombres premiers précédents:

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

Il me semble primes2 devrait être un peu plus rapide que primes1, car elle évite recalcul f_ = f (const True) pour tout entier (que je penser nécessite des travaux de l'ordre du nombre des nombres premiers que nous avons trouvé à ce jour), et il met à jour que lorsque l'on rencontre un nouveau premier.

Juste des tests non scientifiques (en cours d'exécution dans take 1000 ghci) il semble que primes3 tourne plus vite que primes2.

Dois-je prendre une leçon de cela, et supposer que si je peux représenter une fonction comme une opération sur un tableau, que je le mettre en œuvre dans ce dernier de manière à l'efficacité, ou est-il quelque chose d'autre se passe ici?

Answer 1

Quel est le second argument de la f nécessaire pour? À mon avis, ces deux alternatives sont plus lisibles, et ne pas d'impact significatif des performances ...

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

---

Quoi qu'il en soit, revenir à la question. Parfois, l'utilisation des fonctions en tant que structures de données est la meilleure représentation pour une tâche, et parfois pas. « Le meilleur » en termes de facilité de codage et « meilleur » en termes de performance ne sont pas toujours la même chose. Les « fonctions en tant que structures de données » technique est essentielle pour compilation de l'exécution , mais comme cette page met en garde,

  

compilation d'exécution peut parfois vous faire gagner des gains d'efficience, mais peut souvent vous gagner presque rien au prix de votre stress accru et une productivité réduite.

Dans votre cas, il est probable que les frais généraux de la construction de chaque f :: Integer -> ... -> Bool est nettement plus élevé que les frais généraux de la construction de chaque ps :: [Integer], avec une différence peu ou pas lors de l'appel f ... x contre all ... ps.

---

Pour presser les cycles sur le tamis premier infini, se débarrasser des appels à mod! multiplication entier, la division, et le module sont beaucoup plus lents que l'addition et la soustraction entier. Sur ma machine, cette horloge de mise en œuvre à 40% plus rapide lors du calcul des 1000 premiers nombres premiers (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

Dans l'action (en utilisant un bit de syntaxe 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 carte conserve la trace de multiples futurs, en utilisant rien mais plus.

Answer 2

Notez que primes3 peut être rendu plus efficace en changeant ps++[x] à (x:ps). Le (++) en cours d'exécution est linéaire dans la longueur de son argument de gauche, mais constant dans la longueur de l'opérande droit.