[Haskell-cafe] Generate random UArray in constant memory space.
daniel.is.fischer at web.de
Tue Feb 9 07:57:35 EST 2010
Am Dienstag 09 Februar 2010 13:18:23 schrieb Vasyl Pasternak:
> Hello Cafe,
> I tried to generate memory-efficient list of random numbers, so I've
> used uvector library for this task. But it doesn't work,
> it still allocates more than 6Gb of memory for the random list of 10
> million elements. Here is the code:
$ ghc -O2 --make ranVec
[1 of 1] Compiling Main ( ranVec.hs, ranVec.o )
Linking ranVec ...
$ ./ranVec 10000000 +RTS -sstderr
4,919,912,080 bytes allocated in the heap
883,256 bytes copied during GC
26,896 bytes maximum residency (1 sample(s))
25,620 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
maximum residency is just eight bytes more than for 100,000 or 1,000,000
numbers. I think that is constant space.
The ~5 GB total allocation is sequential, ten million new StdGens are
produced and allocated, then immediately garbage collected. I see no
problem (except that StdGen is slow, e.g. the Mersenne twister is much
faster [and allocates less, but still linear in size]).
> > import Text.Printf
> > import System.Random
> > import Control.Applicative
> > import System.Environment
> > import Data.Array.Vector
> > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int)
> > randomListU b g size = unfoldU size gen g
> > where gen g = let (x, g') = randomR b g
> > in JustS (x :*: g')
> > main = do
> > [size] <- map read <$> getArgs
> > let ints = randomListU (-10, 10) (mkStdGen 1) size
> > printf "%d\n" (sumU ints)
> Could someone give a hint, how to implement this function in constant
> memory space?
> Thank you in advance.
> Best regards,
> Vasyl Pasternak
More information about the Haskell-Cafe