On Sat, Oct 13, 2007 at 12:09:57AM +0200, ntupel wrote: > 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.
> setup :: (Ord a, IArray a2 a, IArray a1 e, Num a) => [e] -> [a] -> (a1 Int e, > a1 Int e, a2 Int a) > calcAlias :: (Ord e, Num e, IArray a e, Ix i, IArray a2 e1, IArray a1 e1) => > a2 i e1 -> a1 i e1 -> a i e -> [i] -> [i] -> (a1 i e1, a i e) > next :: (IArray a2 e1, IArray a e1, Ord e, IArray a1 e, RandomGen t, Random > e) => (a Int e1, a2 Int e1, a1 Int e) -> t -> (e1, t) > randomList :: (Random e, RandomGen t1, IArray a2 e, Ord e, IArray a t, IArray > a1 t) => (a Int t, a1 Int t, a2 Int e) -> t1 -> [t] I haven't looked at your code in depth, but these long contexts are something of a red flag. Overloading in Haskell is a very neat mechanism, but it is not really suitable for inner loops; each type class listed turns into an extra parameter, and proxy methods use indirect function calls for the operations (which unfortunately show up in profiles with the same names as the specific operations). I would try specializing to StdGen, UArray, and Int, for RandomGen, IArray, and Random respectively. P.S. Most real programs (outside of specialized niches like Monte-Carlo simulation) spend neglible amounts of time in random number generation. Profile before optimizing! If you've already profiled the real program, ignore this postscript. Stefan
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe