[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