Project Euler (p463) - stderr indica "out of memory"

[thoga31]

Olá, pessoal.

Estava a tentar resolver o problema 463 do Project Euler, e implementei o código que mostro no final.

O problema é que, sempre que tento executar, tenho um problema: demora muito tempo, e excede a memória ao testar no Ideone. Como podem ver, testei a função f para n=100, e obtive 3.96s de execução e o seguinte erro: "prog: out of memory (requested 1048576 bytes)".

Sinceramente não consigo determinar o problema. Espero que possam ter uma pista acerca do possível problema deste código.

Cumprimentos.

f 1 = 1
f 3 = 3
f n | n `elem` c2  = let x = extract2 n
                    in f x
   | n `elem` c41 = let x = extract41 n
                    in 2*f(2*x+1) - (f x)
   | n `elem` c43 = let x = extract43 n
                    in 3*f(2*x+1) - 2*(f x)
   | otherwise    = -1  -- fase de teste
 where
   c2  = map (*2) [1..]
   c41 = map ((+1) . (*4)) [1..]
   c43 = map ((+3) . (*4)) [1..]

   extract2  = (`div` 2)
   extract41 = (`div` 4) . subtract 1
   extract43 = (`div` 4) . subtract 3

euler463 n = sum . take n . map f $ [1..]

main = do
 writeln 8
 -- writeln 100
 -- writeln (3^37)
   where
     writeln = putStrLn . show . f  -- substituir "f" por "euler463" quando o problema for resolvido

Edited March 22, 2014 by thoga31

[brunoais]

Vais ter que forçar a execução do que ele tem em estado de espera. O que se passa é que ele está a juntar imensos dados à lista de execução.

Usa a função $! (forced execution) para evitar isso.

[pwseo]

A solução não deve ser apenas por aí. Mesmo com strictness, continuamos a ter de aplicar a função f 3^37 vezes, e cada uma delas pode ramificar na aplicação recursiva de si mesma.

Com strictness evitamos o out of memory, mas continuamos sem solução do problema em tempo útil.

[Baderous]

Guarda os resultados intermédios de cada cálculo de f n, assim já podes aceder em tempo constante a esses resultados em vez de os estares a calcular para cada i do somatório.

[thoga31]

Ontem calhou em conversa com o @pwseo falar acerca deste problema por outros meios, ao que ele me sugeriu olhar para este código e comparar com o meu:

f :: Integer -> Integer
f 1 = 1
f 3 = 3
f n | mod n 2 == 0        = f n1
   | mod (n - 1) 4 == 0  = 2 * (f (2 * n2 + 1)) - (f n2)
   | mod (n - 3) 4 == 0  = 3 * (f (2 * n2 + 1)) - 2 * (f n2)
 where
   n1 = div n 2
   n2 = div n 4

s :: Integer -> Integer
s n = sum . map f $ [1..n]

Estava com sérios problemas de optimização - aquele carregamento de maps, entre outras coisas, estava a esgotar recursos demasiadamente depressa.

A partir deste código já estou a estudar as severas diferenças de gasto de memória para aprender a optimizar a este nível.

Obrigado a todos pelas sugestões, vou também experimentar cada uma delas 😉