From ac4f723e8b6b72a0b23642c72c9c4e32909d209f Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Mon, 5 Oct 2009 11:55:15 +0000 Subject: make it faster, replace queue with array --- weasel.c | 63 ++++++++++++++++++++++++++++++--------------------------------- 1 file changed, 30 insertions(+), 33 deletions(-) diff --git a/weasel.c b/weasel.c index 21cd3a2..fc386c6 100644 --- a/weasel.c +++ b/weasel.c @@ -15,7 +15,6 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ -#include #include #include #include @@ -44,14 +43,12 @@ const char alphabet[] = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEEFGHIJKLMNOPQRST const char *aim; -SLIST_HEAD(creatures, creature) generation; struct creature { char *genom; int length; float fitness; int locked; - SLIST_ENTRY(creature) link; -} *cp; +} *cp, **generation; char rndchar() @@ -75,11 +72,12 @@ calculatefitness(char *genom, int length) void initpopulation(int length, int number) { - int i; + int i, n; - SLIST_INIT(&generation); + generation = calloc(number, sizeof(struct creature *)); + assert(generation); - while (number-- > 0) { + for (n = 0; n < number; n++) { cp = malloc(sizeof(struct creature)); assert(cp); cp->genom = malloc(length + 1); @@ -90,7 +88,7 @@ initpopulation(int length, int number) cp->length = length; cp->fitness = calculatefitness(cp->genom, cp->length); cp->locked = 0; - SLIST_INSERT_HEAD(&generation, cp, link); + generation[n] = cp; } } @@ -101,12 +99,14 @@ printcreature(struct creature *c) } void -printpopulation(int maximal) +printpopulation(int maximal, int number) { + int n; + printw("%1.3f\t%s\n\n", 1.0, aim); - SLIST_FOREACH(cp, &generation, link) { - printcreature(cp); - if (maximal-- <= 0) + for (n = 0; n < number; n++) { + printcreature(generation[n]); + if (n >= maximal) break; } printw("\n"); @@ -120,10 +120,7 @@ pickrandom(int population) for (;;) { n = random() % population; - SLIST_FOREACH(cp, &generation, link) - if (n-- <= 0) - break; - + cp = generation[n]; if (cp->locked) continue; @@ -152,9 +149,14 @@ cmp(const void *u, const void *v) return 0; } -void -intercourse(int population, int mutationsrate) +void * +intercourse(void *args) { + + struct intargs *ia = args; + int population = ia->population; + int mutationsrate = ia->mutationrate; + struct creature *c[3]; int i; @@ -176,20 +178,25 @@ intercourse(int population, int mutationsrate) c[0]->locked = 0; c[1]->locked = 0; c[2]->locked = 0; + + pthread_exit(NULL); } int -success() +success(int number) { struct creature *best = NULL; float fittest = 0; + int n; /* find best */ - SLIST_FOREACH(cp, &generation, link) + for (n = 0; n < number; n++) { + cp = generation[n]; if (cp->fitness > fittest) { fittest = cp->fitness; best = cp; } + } assert(best); printcreature(best); @@ -197,16 +204,6 @@ success() return best->fitness == 1.0; } -void * -ptintercourse(void *args) -{ - struct intargs *ia = args; - - intercourse(ia->population, ia->mutationrate); - - pthread_exit(NULL); -} - void usage(void) { @@ -280,9 +277,9 @@ main(int argc, char **argv) for (i = 0;; i++) { move(0, 0); for (t = 0; t < nthreads; t++) - pthread_create(&threads[t], &attr, ptintercourse, (void *)&args); - printpopulation(LINES - 8); - if (success()) + pthread_create(&threads[t], &attr, intercourse, (void *)&args); + printpopulation(LINES - 8, population); + if (success(population)) break; refresh(); } -- cgit v1.2.3