Como melhorar a eficiência com a programação funcional?

Recentemente, eu passei pelo guia Aprenda um Haskell para o bem grande e, como prática, queria resolver o problema do Projeto Euler 5 com ele, que especifica:

Qual é o menor número positivo que é igualmente divisível por todos os números de 1 a 20?

Decidi primeiro escrever uma função determinando se um determinado número é divisível por esses números:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Depois calculei o menor usando head:

sm = head [x | x <- [1..], divisable x]

E finalmente escreveu a linha para exibir o resultado:

main = putStrLn $ show $ sm

Infelizmente, isso levou cerca de 30 segundos para terminar. Fazer o mesmo com os números de 1 a 10 gera um resultado quase imediatamente, mas, novamente, o resultado é muito menor que a solução de 1 a 20.

Eu o resolvi anteriormente em C e lá o resultado de 1 a 20 também foi calculado quase instantaneamente. Isso me leva a acreditar que estou entendendo mal como interpretar esse problema para Haskell. Examinei as soluções de outras pessoas e descobri o seguinte:

main = putStrLn $ show $ foldl1 lcm [1..20]

É justo, isso usa uma função interna, mas por que o resultado final é muito mais lento quando você faz isso sozinho? Os tutoriais por aí mostram como usar o Haskell, mas não vejo muita ajuda na transformação de algoritmos em código rápido.

Primeiro, você precisa ter um binário otimizado, antes de pensar que o idioma é o problema. Leia o capítulo Criação de perfil e otimização no Real Wolrd Haskell. Vale ressaltar que, na maioria dos casos, a natureza de alto nível do idioma custa pelo menos parte do desempenho.

No entanto, observe que a outra solução não é mais rápida porque usa uma função interna, mas simplesmente porque utiliza um algoritmo muito mais rápido : para encontrar o múltiplo menos comum de um conjunto de números, você precisa encontrar apenas alguns GCDs. Compare isso com a sua solução, que percorre todos os números de 1 a foldl lcm [1..20]. Se você tentar com 30, a diferença entre os tempos de execução será ainda maior.

Dê uma olhada nas complexidades: seu algoritmo tem O(ans*N)tempo de execução, onde ansestá a resposta e Né o número até o qual você está verificando a divisibilidade (20 no seu caso).
O outro algoritmo executa Ntempos lcm, no entanto lcm(a,b) = a*b/gcd(a,b), e o GCD tem complexidade O(log(max(a,b))). Portanto, o segundo algoritmo tem complexidade O(N*log(ans)). Você pode julgar por si mesmo o que é mais rápido.

Então, para resumir:
Seu problema é seu algoritmo, não a linguagem.

Observe que existem linguagens especializadas, funcionais e focadas em programas pesados ​​em matemática, como o Mathematica, que para problemas focados em matemática é provavelmente mais rápido do que quase qualquer outra coisa. Possui uma biblioteca de funções muito otimizada e suporta o paradigma funcional (é certo que também suporta programação imperativa).

Meu primeiro pensamento foi que apenas os números divisíveis por todos os números primos <= 20 serão divisíveis por todos os números menores que 20. Portanto, você só precisa considerar números que são múltiplos de 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 . Essa solução verifica 1 / 9.699.690 tantos números quanto a abordagem da força bruta. Mas sua solução rápida-Haskell se sai melhor que isso.

Se eu entendo a solução "rápida Haskell", ela usa foldl1 para aplicar a função lcm (mínimo múltiplo comum) à lista de números de 1 a 20. Portanto, aplicaria lcm 1 2, produzindo 2. Em seguida, lcm 2 3 produz 6 Então lcm 6 4 rendendo 12, e assim por diante. Dessa forma, a função lcm é chamada apenas 19 vezes para fornecer sua resposta. Na notação Big O, são operações O (n-1) para chegar a uma solução.

Sua solução Haskell lenta percorre os números de 1 a 20 para cada número de 1 à sua solução. Se chamarmos a solução s, a solução lenta-Haskell executa operações O (s * n). Já sabemos que s é superior a 9 milhões, o que provavelmente explica a lentidão. Mesmo que todos atalhos atinjam a média da lista de números de 1 a 20, isso ainda é apenas O (s * n / 2).

A chamada headnão impede que você faça esses cálculos, eles precisam ser feitos para calcular a primeira solução.

Obrigado, essa foi uma pergunta interessante. Isso realmente ampliou meu conhecimento sobre Haskell. Eu não seria capaz de responder se não tivesse estudado algoritmos no outono passado.

Inicialmente, eu não estava pensando em escrever uma resposta. Mas fui informado de que depois que outro usuário fez a estranha afirmação de que simplesmente multiplicar os dois primeiros números primos era mais caro em termos de computação do que aplicar repetidamente lcm. Então, aqui estão os dois algoritmos e alguns benchmarks:

Meu algoritmo:

Algoritmo de geração principal, fornecendo uma lista infinita de números primos.

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n 
    | isPrime n = n 
    | otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes

Agora, usando essa lista principal para calcular o resultado para alguns N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Agora, o outro algoritmo baseado no lcm, que é bastante conciso, principalmente porque implementei a geração principal do zero (e não usei o algoritmo de compreensão da lista super concisa devido ao seu baixo desempenho), ao passo que lcmfoi simplesmente importado do Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Agora, para os benchmarks, o código que usei para cada um era simples: ( -prof -fprof-auto -O2então +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Para n = 100,000, solvePrime:

total time = 0.04 secs
total alloc = 108,327,328 bytes

vs solveLcm:

total time = 0.12 secs
total alloc = 117,842,152 bytes

Para n = 1,000,000, solvePrime:

total time = 1.21 secs
total alloc = 8,846,768,456 bytes

vs solveLcm:

total time = 9.10 secs
total alloc = 8,963,508,416 bytes

Para n = 3,000,000, solvePrime:

total time = 8.99 secs
total alloc = 74,790,070,088 bytes

vs solveLcm:

total time = 86.42 secs
total alloc = 75,145,302,416 bytes

Eu acho que os resultados falam por si.

O criador de perfil indica que a geração principal ocupa uma porcentagem cada vez menor do tempo de execução à medida que naumenta. Portanto, não é o gargalo, então podemos ignorá-lo por enquanto.

Isso significa que estamos realmente comparando a chamada em lcmque um argumento vai de 1 para ne o outro vai geometricamente de 1 para ans. Telefonar *com a mesma situação e o benefício adicional de pular todos os números não primos (assintoticamente de graça, devido à natureza mais cara *).

E é sabido que *é mais rápido do que lcm, pois lcmrequer aplicações repetidas de mode modé assintoticamente mais lento ( O(n^2)vs ~O(n^1.5)).

Portanto, os resultados acima e a breve análise do algoritmo devem tornar muito óbvio qual algoritmo é mais rápido.