[clean-list] MersenneTwister --- fixing the program

Pieter Koopman pieter at cs.ru.nl
Mon Oct 19 08:49:27 MEST 2009


Dear Philippos,

In order to test the MersenneTwister library I wrote the following tiny 
program and included some measurements. This shows that this program 
checks nearly 10^7 intergers/second and about half of this number for 
reals. Since reals are constructed from the integers in the Mersenne 
Twister library, this is not surprising. The speed is pretty independent 
of the number of elements used.
- do you have a random library that is significant faster?
- MersenneTwister is a pretty complicated algorithm to generate high 
quality pseudo random numbers, this might take some time. Does your 
library generate pseudo random numbers that are equally 'random'?
- I dod not look into your converge problem, some explenation of your 
program would make that easier. In general converge in genetic problems 
might be quite sensitive for the random numbers used. Obtaining 
different results for different random generators is not always a sign 
that something is wrong. First try to do the easy thing: is there 
something wrong with mersenneTWister.

Best,

Pieter Koopman

module mtTest

import StdEnv, MersenneTwister

Start = testReal 10000000

/*
Int
100000      Execution: 0.01  Garbage collection: 0.00  Total: 0.01
1000000     Execution: 0.12  Garbage collection: 0.00  Total: 0.12
10000000    Execution: 1.12  Garbage collection: 0.03  Total: 1.15
100000000    Execution: 11.05  Garbage collection: 0.37  Total: 11.43
1000000000    Execution: 105.44  Garbage collection: 2.82  Total: 108.26

Real
100000      Execution: 0.03  Garbage collection: 0.00  Total: 0.03
1000000     Execution: 0.28  Garbage collection: 0.01  Total: 0.29
10000000    Execution: 2.37  Garbage collection: 0.06  Total: 2.43
100000000    Execution: 24.41  Garbage collection: 0.79  Total: 25.20
1000000000    Execution: 232.04  Garbage collection: 7.61  Total: 239.66
*/

count :: !Int !Int !Int ![n] -> (!Int,!Int) | <, zero n
count 0 s l rs = (s,l)
count n s l [r:rs]
    | r < zero
        = count (n-1) (s+1) l rs
        = count (n-1) s (l+1) rs

testInt :: !Int -> (!Int,!Int)
testInt n = count n 0 0 (genRandInt 42)

testReal :: !Int -> (!Int,!Int)
testReal n = count n 0 0 (genRandReal 42)

Philippos Apolinarius wrote:
> My previous program has quite a few bugs. I fixed them in the program 
> below. However, both programs are very slow in Clean. As I told 
> before, I believe that the problem lies in the Mersennetwister 
> library. In order to see how slow it is, change the population size to 
> something like 5000.
>
>
> module gp;
> import StdEnv, MersenneTwister, ArgEnv, StdTime;
>
> :: Op = AND | OR | NOT;
> :: Tree= L Int | T Op [Tree];
> ::TT :== [(Bool,Bool,Bool)];
> ::Stt= !{ psz::Int, beastSz::Int, seed::[Int],
>          thr::Real, fs::[Op]};
>         
> table= [(False, False, False),
>             (True, False, True),
>             (True, True, False),
>             (False, True, True)];
>
> Start w
>   # (ct,w)= getCurrentTime w;
>     seed= 1+ct.seconds+ct.minutes*60;
>     xs= genRandInt seed;
>     st = { psz=popsz,beastSz=5, seed= xs, 
>            fs= [OR, AND, NOT], thr=4.0};
>     (p, st) = gen0 population st;
>     (gate, st)= evolve 30 p (L 0) st;
>   = gate;
> where {
>   popsz= 50;
>   population :: .{!Tree};
>   population = createArray popsz (L 0);
> }
> rn n st=:{seed}
>  # [x:seed] = seed;
>  = ((abs x) rem n, {st&seed= seed});
> rnLen (T _ s) st= rn (length s) st;
>
> nGates (L i)= 0.0;
> nGates (T p xs) = -0.1 + sum[nGates g \\ g <- xs];
>
> run :: Tree {Bool} -> Bool;// Interpreter
> run (L i) v= v.[i];
> run (T AND xs) v = and [run c v \\ c <- xs];
> run (T OR xs) v= or [run c v \\ c <- xs];
> run (T NOT [t:_]) v= not (run t v);
>
> mutate e (L i, st) = (e, st);
> mutate e (t, st) = ins t (rnLen t st) where {
>   ins (T p [x:xs]) (n, st) | n > 0
>     # (T _ mt, st)= ins (T p xs) (n-1, st);
>     = (T p [x:mt], st);
>   ins (T p [L i:xs]) (0, st)=(T p[e:xs], st);
>   ins (T p [t:xs]) (0,st)
>     # (coin, st)= rn 2 st
>     | coin==0 = (T p [e:xs], st);
>     # (xpr, st)= mutate e (t, st);
>     = (T p [xpr:xs], st); }
>
> crossover e1 e2 st
>     # (g1, st) = frag (e1, st);
>       (g2, st) = frag (e2, st);
>       (c1, st) = mutate g1 (e2, st);
>       (c2, st) = mutate g2 (e1, st);
>     = ([c2, c1], st) where{
>   frag (L i, st) = (L i, st);
>   frag (T p xs, st)
>     # (n, st)= rnLen (T p xs) st;
>       # xpr = xs!!n;
>       # (coin, st)= rn 2 st;
>     | coin== 0=  (xpr, st);
>     = frag (xpr, st); }
>
> rndXpr st=:{fs, beastSz}= loop beastSz st where {
>   rth s st
>   # (n, st) = rn (length s) st;
>   = (s!!n, st);
>   fxy NOT st
>   # (n, st)= rn 2 st;
>   = (T NOT [L n], st);
>   fxy AND st = (T AND [L 0, L 1], st);
>   fxy OR  st = (T OR  [L 0, L 1], st);
>   loop n st | n<1
>    # (fn, st)= rth fs st;
>    # (f, st)= fxy fn st;
>    = (f, st);
>   loop n st
>    # (f1, st) = loop (n-1) st;
>    # (fn, st) = rth fs st;
>    # (e, st) = fxy fn st;
>    = mutate e (f1, st); }
>
> gen0 population st=:{psz, fs}= loop population 0 st where {
>    loop p i st | i >= size p = (p, st);
>    loop p i st
>      # (g, ts)= rndXpr st;
>      = loop {p&[i]=g}  (i+1) st;}
>
> fitness gt= ng+1.0+sum[ft t \\ t <- table]
> where{ ng= nGates gt;
>    ft (out, t1, t2) | run gt {t1, t2} == out= 1.0;
>    ft _ = 0.0; }
>      
> evolve n p b st | n < 1
>   # (p, st)= gen0 p st;
>   = evolve 30 p b st;
> evolve n p b st=:{thr, fs, psz}
>   # (n1, st)= rn psz st;
>     (n2, st)= rn psz st;
>     (g1, p) = p![n1];
>     (g2, p) = p![n2];
>     ([c1, c2:_], st) = crossover g1 g2 st;
>     p= insrt c1 p 0 psz;
>     p= insrt c2 p 0 psz;
>     (g, p)= best 0 b p;
>     f= fitness g;
>   | f>thr = (g, st);
>   = evolve (n-1) p b st;
>  
>   best i res p | i >= size p= (res, p);
>   best i fg1 p =:{[i]=fg}
>     | (fitness fg) > (fitness fg1) = best (i+1) fg p;
>     = best (i+1) fg1 p;
>    
>   insrt g v i sz | i >= sz = v;
>   insrt g v=:{[i]=a} i sz
>     | (fitness g) > (fitness a) = {v&[i]=g};
>     = insrt g v (i+1) sz;
>
>
> ------------------------------------------------------------------------
> Get the name you've always wanted <http://ca.promos.yahoo.com/jacko/>! 
> *@ymail.com *or *@rocketmail.com*.
> ------------------------------------------------------------------------
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list
>   


More information about the clean-list mailing list