[Haskell-cafe] Performance problem with random numbers
ntupel
ntupel at googlemail.com
Fri Oct 12 18:09:57 EDT 2007
Dear all,
I have implemented a small module to generate random items with a given
probability distribution using the alias approach [1] and unfortunately
compared to similar implementations in C++ or Java it is about 10 times
slower. I have to confess that I am still in the early stages of writing
Haskell programs so there is hopefully something I can do about it and I
hope some helpful soul on this list can give me a hint.
I have attached my implementation and a small testing routine which runs
in about 5 seconds on my machine (when compiled with -O2) whereas my
Java-Implementation finishes in about 0.48 seconds. Profiling indicates
that the time is mostly spend in System.Random.random and
System.Random.randomR so I wonder if these are slow or what else might
cause the relative slowness of my implementation.
Many thanks for your responses,
Thoralf
PS: I would also appreciate any feedback about the module from a design
perspective. I bet I miss lots of good Haskell idioms.
----------------
[1] The alias methods moves probability mass of a non-uniform
probability distribution around to create a uniform distribution. Lets
say you have three items "a", "b", and "c" with distribution [0.2, 0.1,
0.7] then a uniform distribution would assign 1/3 to each so "a" and "b"
need to be "filled up" with exactly the same probability mass that "c"
has too much. Then 2 uniform random numbers are generated. The first one
to pick an item and the second one to pick either the item itself if the
value is in the original part or the alias otherwise. A much better
explanation can be found on the web somewhere. Anyway it should not
matter with regards to the performance problem I have.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.hs
Type: text/x-haskell
Size: 394 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071013/d92db797/main-0001.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: random.hs
Type: text/x-haskell
Size: 2735 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071013/d92db797/random-0001.bin
More information about the Haskell-Cafe
mailing list