estilo Haskell / eficiência

Question

Então, eu estava trabalhando em uma maneira de gerar preguiçosamente primos, e eu vim com essas três definições, que todo o trabalho de forma equivalente - basta verificar se cada novo número inteiro tem um fator entre todos os 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

Assim, parece-me primes2 deve ser um pouco mais rápido do que primes1, uma vez que evita recalcular f_ = f (const True) para cada inteiro (que eu pensar requer trabalho na ordem do número de primos que nós encontramos até agora), e só atualiza-lo quando nos deparamos com um novo auge.

Apenas a partir de testes não-científicas (em execução take 1000 em ghci) parece que corre primes3 mais rápidos que primes2.

Devo tomar uma lição com isso, e assumir que se eu posso representar uma função como uma operação em uma matriz, que eu deveria implementá-lo na última forma para a eficiência, ou há algo outra coisa acontecendo aqui?

Answer 1

O que é o segundo argumento para o f é necessário para? Na minha opinião, essas duas alternativas são mais legível, e não significativamente o desempenho impacto ...

...
            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 qualquer forma, de volta à questão. Às vezes, o uso de funções como estruturas de dados é a melhor representação para uma determinada tarefa, e às vezes não. "Melhor" em termos de facilidade de codificação e "melhor" em termos de desempenho nem sempre são a mesma coisa. Os "funciona como estruturas de dados" técnica é essencial para runtime compilação , mas como essa página adverte:

Runtime compilação às vezes pode ganhar-lhe ganhos de eficiência significativos, mas muitas vezes você pode ganhar quase nada à custa do seu aumento do estresse e redução da produtividade.

No seu caso, é provável que a sobrecarga de construir cada f :: Integer -> ... -> Bool é significativamente maior do que a sobrecarga de construir cada ps :: [Integer], com pouca ou nenhuma diferença quando chamando f ... x contra all ... ps.

---

Para espremer ciclos fora da peneira nobre infinito, se livrar das chamadas para mod! Inteiros de multiplicação, divisão, e o módulo são muito mais lenta do que a adição e subtracção inteiro. Na minha máquina, este relógios de implementação em pelo 40% mais rápido ao calcular os primeiros 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

Na ação (usando um pouco de sintaxe 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]}
...

o mapa mantém informado dos futuros múltiplos, usando nada além disso.

Answer 2

Note que primes3 pode ser mais eficiente mudando ps++[x] para (x:ps). O (++) de execução é linear no comprimento de seu argumento esquerda, mas constante no comprimento do argumento direita.