2009-05-22 11 views
6

Así que estaba trabajando en una forma de generar primos de forma perezosa, y se me ocurrieron estas tres definiciones, que funcionan todas de manera equivalente, simplemente comprobando si cada nuevo entero tiene un factor entre todos los anteriores primos:Haskell style/efficiency

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ían ser un poco más rápido que primes1, ya que evita recomputing f_ = f (const True) para cada entero (que que requiere un trabajo en el orden del número de números primos que lo he encontrado hasta ahora), y solo lo actualiza cuando enc ounter un nuevo primo.

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

¿Debo tomar una lección de esto, y asumamos 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í ?

+0

(como estoy seguro ya sabes) en 'primes3' aquí llamando' all' es una exageración enorme - tomar únicamente primos no superiores a 'sqrt' de' x' es suficiente - así se puede usar la misma lista de primos que se está construyendo - la función se convierte en filtro simple: 'primes4 = 2: filtro (\ x-> all ((/ = 0). (rem x)) $ takeWhile ((<= x). (^ 2)) primes4) [3,5 ..] ', ejecutando aproximadamente' O (n^1.45) 'empíricamente, en' n' primos producidos - * las tres * versiones en su pregunta se ven cuadráticas - no importa cómo construya sus funciones, todavía prueba con * todos * primos en lugar de solo aquellos debajo de 'sqrt x'. –

Respuesta

9

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


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

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

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 exprimir a cabo ciclos de la criba primer infinita, deshacerse de las llamadas a mod! La multiplicación, división y módulo enteros son mucho más lentos que la suma y resta entera. En mi máquina, esta implementación entra un 40% más rápido cuando se calculan los primeros 1000 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 (con 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.

+0

¡Gracias! Este es el tipo de respuesta detallada que esperaba. – rampion

+0

solo una nota al margen: esto [se puede mejorar significativamente] (http://hpaste.org/79571) al retrasar la adición de cada primo en el mapa hasta que se vea el cuadrado de ese primo en la entrada, como se ve, por ejemplo. [aquí en Python] (http://stackoverflow.com/a/10733621/849891). también compare http://stackoverflow.com/a/13895347/849891. –

1

Tenga en cuenta que primes3 se puede hacer más eficiente cambiando ps++[x] a (x:ps).La ejecución de (++) es lineal en la longitud de su argumento de la izquierda, pero constante en la longitud del argumento de la derecha.

+3

En realidad, eso fue intencional. 2 es un factor mucho más frecuente que 173, por lo que obtenemos más salidas anticipadas cuando buscamos primalidad cuando comenzamos desde el extremo más pequeño que desde el extremo grande. – rampion