Sorry, maybe I should ask more clearer. I've looked at dons article "Haskell as fast as C"[1], and tried to implement similar algorithm but for list of random numbers. Please look at code:
import Text.Printf import Control.Applicative import System.Environment import Data.Array.Vector
main = do [size] <- map read <$> getArgs let ints = enumFromToU 0 size :: UArr Int printf "%d\n" (sumU ints)
This code runs in constant space (on my pc ~25kb allocates on the
heap) regardless of array size. So I tried to achieve similar with
random list, just to replace `enumFromToU` with my own list generator.
So the question - is it possible to implement random list similary to
enumFromToU?
[1]http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-hi...
Thank you,
Vasyl Pasternak
2010/2/9 Daniel Fischer
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:
Hmm,
$ ghc -O2 --make ranVec [1 of 1] Compiling Main ( ranVec.hs, ranVec.o ) Linking ranVec ... $ ./ranVec 10000000 +RTS -sstderr 5130 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