haskell-cafe@haskell.org
[Top] [All Lists]

[Haskell-cafe] Performance problem with random numbers

Subject: [Haskell-cafe] Performance problem with random numbers
From: ntupel
Date: Sat, 13 Oct 2007 00:09:57 +0200
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.

Attachment: main.hs
Description: Text Data

Attachment: random.hs
Description: Text Data

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/haskell-cafe
<Prev in Thread] Current Thread [Next in Thread>