Jump to content

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


thoga31
 Share

Recommended Posts

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 by thoga31

Knowledge is free!

Link to comment
Share on other sites

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.

"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 😉

Knowledge is free!

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.