stilo / eficiência Haskell
ntão, eu estava trabalhando em uma maneira de gerar primos preguiçosamente, e criei essas três definições, que funcionam de maneira equivalente - apenas verificando se cada novo número inteiro tem um fator entre todos os primos anteriore
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
Então me pareceprimes2
deve ser um pouco mais rápido queprimes1
, pois evita a recálculof_ = f (const True)
para cada número inteiro (que eupensa requer um trabalho na ordem do número de números primos que encontramos até agora) e somente o atualiza quando encontramos um novo número prim
Apenas a partir de testes não científicos (executandotake 1000
em ghci) parece queprimes3
corre mais rápido queprimes2
.
Devo tirar uma lição disso e supor que, se eu puder representar uma função como uma operação em uma matriz, devo implementá-la da última maneira para obter eficiência, ou há alguma outra coisa acontecendo aqui?