estilo Haskell / eficiencia

Question

Así que yo estaba trabajando en una forma de generar números primos con pereza, y se me ocurrió con estas tres definiciones, que todo el trabajo de forma equivalente - simplemente comprobar si cada nuevo número entero tiene un factor de entre todos los números primos anteriores:

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

Así que me parece primes2 debería ser un poco más rápido que primes1, ya que evita recalcular f_ = f (const True) para cada entero (que I pensar requiere un trabajo en el orden de los números de números primos que hemos encontrado hasta ahora), y sólo se actualiza cuando nos encontramos con un nuevo primer.

Sólo a partir de pruebas no científicas (correr take 1000 en ghci) parece que funciona más rápido primes3 que primes2.

¿Debo tomar una lección de esto, y asumir que si puedo representar una función como una operación en una matriz, que debería ponerlo en práctica en esta última forma de la eficiencia, o hay algo más en juego aquí?

Answer 1

¿Cuál es el segundo argumento de la necesaria para f? En mi opinión, ambas de estas alternativas son más legible, y no afectan significativamente el rendimiento ...

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

---

De todos modos, volviendo a la pregunta. A veces, el uso de funciones como estructuras de datos es la mejor representación para una tarea determinada, y otras no. "Mejor" en términos de facilidad de codificación y "mejor" en términos de rendimiento no siempre son la misma cosa. La técnica "funciona como estructuras de datos" es esencial para tiempo de ejecución compilación , pero a medida que la página advierte,

  

compilación en tiempo de ejecución a veces se puede ganar importantes ganancias de eficiencia, pero a menudo se puede ganar casi nada a costa del aumento del estrés y su reducción de la productividad.

En su caso, es probable que la sobrecarga de la construcción de cada uno f :: Integer -> ... -> Bool es significativamente mayor que la sobrecarga de la construcción de cada uno ps :: [Integer], con poca o ninguna diferencia cuando se llama a f ... x frente all ... ps.

---

Para apretar los ciclos de la criba primer infinita, deshacerse de las llamadas a mod! multiplicación de enteros, división, y el módulo son mucho más lentos que la adición número entero y la resta. En mi máquina, esta implementación los relojes en 40% más rápido en el cálculo de los 1000 primeros números primos (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

En la acción (usando un poco de sintaxis 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]}
...

el mapa realiza un seguimiento de las futuras múltiplos, usando nada más que la suma.

Answer 2

Tenga en cuenta que primes3 puede hacerse más eficiente mediante el cambio ps++[x] a (x:ps). El (++) de ejecución es lineal en la longitud de su argumento izquierdo, pero constante en la longitud del argumento de la derecha.