Hi MailList Haskell-Cafe: I am tring to solve Project Euler problem 70. And write some code. (will at the end of this mail) And, I run the code in GHCi. The problem is that, when the input is 1,000,000, it works fine, when the input is up to 10,000,000, the memory GHCi used increase very fast and did not stop. Is this a memory leak ? or, is there some mis-understand about array ? Regards -------------- -- Mudules : import Data.Array.IO import Foreign ( unsafePerformIO ) -- Codes : p070_solve = putStrLn . show $ solutionOf 10000000 where isPerm a b = sort (show a) == sort (show b) phis n = unsafePerformIO $ do arr <- newArray (2,n) (False,1/1) :: Fractional t => IO (IOArray Int (Bool,t)) mapM_ (sieve arr n) [2..n] factors <- getElems arr return . map (\(n,(b,f)) -> (n,floor $ toRational n*f)) $ zip [2..n] factors where sieve arr ubound p = do (b,o) <- readArray arr p if b then return () else mapM_ (update arr (toRational p)) . takeWhile (<=ubound) $ iterate (+p) p update arr p i = do (_,o) <- readArray arr i writeArray arr i (True,o*(p-1)/p) solutionOf = snd . minimum . map (\(n,phi)->(toRational n / toRational phi,n)) . filter (uncurry isPerm) . phis -------------- L.Guo 2007-09-14
On 9/14/07, L.Guo
Hi MailList Haskell-Cafe:
I am tring to solve Project Euler problem 70. And write some code. (will at the end of this mail) And, I run the code in GHCi.
The problem is that, when the input is 1,000,000, it works fine, when the input is up to 10,000,000, the memory GHCi used increase very fast and did not stop.
Is this a memory leak ? or, is there some mis-understand about array ?
Haskell's boxed arrays are non-strict, which can cause space leaks when you don't actually need the laziness. The usual quick-&-dirty solution is to switch to unboxed arrays (e.g. IOUArray), which are inherently strict, but they're only available for certain primitive element types. The solution, then, is to make sure you adequately force your thunks before storing them in an array.
update arr p i = do (_,o) <- readArray arr i writeArray arr i (True,o*(p-1)/p)
Here's a possible fix, though it's untested, and I'm sure there are more elegant ways to write it: update arr p i = do (_, o) <- readArray arr i let val = o * (p-1) / p val `seq` return () -- force the thunk writeArray arr i (True, val) This ensures that the second component of the pair is a value, rather than a thunk. Strictifying data such as numbers and booleans is relatively easy, but things get tricky when you try to force more complicated structures (deepSeq, anyone?). Stuart
Hi Stuart. Thanks for your advice about thunk, though I do not understand *thunk* very well. Is there any other discriptions about thunk ? I have tried the *seq* operation. When input is 10,000,000, the memory still "leak", and there is still a "stack overflow". I changed some mapM_ to sequence . map f, and tried to save some division. The key functions now looks like this: proportions n = unsafePerformIO $ do arr <- newArray (2,n) (False,1/1) :: Fractional t => IO (IOArray Int (Bool,t)) sequence_ $ map (sieve arr n) [2..n] factors <- getElems arr return . map (\(n,(b,f)) -> (f,n)) $ zip [2..n] factors where sieve arr ubound p = do (b,o) <- readArray arr p if b then return () else sequence_ . map (update arr (toRational p)) . takeWhile (<=ubound) $ iterate (+p) p update arr p i = do (_,o) <- readArray arr i --writeArray arr i (True,o*(p-1)/p) let val = o * p / (p-1) val `seq` return () -- force the thunk writeArray arr i (True, val) solutionOf = snd . minimum . filter (\(f,n) -> isPerm (floor $ toRational n/f) n) . proportions ------------------ L.Guo 2007-09-15
On Sep 14, 2007, at 21:35 , L.Guo wrote:
Thanks for your advice about thunk, though I do not understand *thunk* very well. Is there any other discriptions about thunk ?
A "thunk" is, in general, a piece of code which represents a suspended or delayed action. In Haskell, it represents a lazy computation: Haskell will only evaluate the code if the value is actually needed, and even then only just enough to satisfy the immediate need (thus, the result of evaluating a thunk may be a value, or another thunk). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
participants (3)
-
Brandon S. Allbery KF8NH -
L.Guo -
Stuart Cook