X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn-evolution-cut.c;h=bb3c9abc95e9704370d35ecf5af95bce062fb97d;hp=f33e873744f94ce3e47fcac80566862d3e6064f2;hb=ea03c7deb7078b4e08af1d248ba78a32d40ddd3c;hpb=43b2d773faa36a7c6135cf814b69f53d2086081f diff --git a/src/sn-evolution-cut.c b/src/sn-evolution-cut.c index f33e873..bb3c9ab 100644 --- a/src/sn-evolution-cut.c +++ b/src/sn-evolution-cut.c @@ -34,6 +34,7 @@ #include #include #include +#include #include @@ -65,6 +66,9 @@ static int evolution_threads_num = 4; static int do_loop = 0; static uint64_t iteration_counter = 0; +static uint64_t max_iterations = 0; + +static int target_rating = 0; static void sigint_handler (int signal __attribute__((unused))) { @@ -82,6 +86,9 @@ static void exit_usage (const char *name) " -p Size of the population (default: 128)\n" " -P Send individuals to (may be repeated)\n" " -t Number of threads (default: 4)\n" + " -n Maximum number of steps (iterations) to perform\n" + " -r Target rating: Stop loop when rating is less then or equal\n" + " to this number.\n" "\n", name); exit (1); @@ -91,7 +98,7 @@ int read_options (int argc, char **argv) /* {{{ */ { int option; - while ((option = getopt (argc, argv, "i:o:O:p:P:s:t:h")) != -1) + while ((option = getopt (argc, argv, "i:o:O:p:P:s:t:n:r:h")) != -1) { switch (option) { @@ -159,6 +166,29 @@ int read_options (int argc, char **argv) /* {{{ */ break; } + case 'n': + { + errno = 0; + max_iterations = (uint64_t) strtoull (optarg, + /* endptr = */ NULL, + /* base = */ 0); + if (errno != 0) + { + fprintf (stderr, "Parsing integer argument failed: %s\n", + strerror (errno)); + exit_usage (argv[0]); + } + break; + } + + case 'r': + { + int tmp = atoi (optarg); + if (tmp > 0) + target_rating = tmp; + break; + } + case 'h': default: exit_usage (argv[0]); @@ -168,41 +198,12 @@ int read_options (int argc, char **argv) /* {{{ */ return (0); } /* }}} int read_options */ -static int apply_cut (sn_network_t *n, int input) /* {{{ */ -{ - enum sn_network_cut_dir_e dir = DIR_MAX; - - if (input < 0) - { - dir = DIR_MIN; - input *= (-1); - } - input--; - - return (sn_network_cut_at (n, input, dir)); -} /* }}} int apply_cut */ - -static int apply (sn_network_t *n, const individuum_t *ind) /* {{{ */ -{ - int i; - - for (i = 0; i < cuts_num; i++) - apply_cut (n, ind[i]); - - return (0); -} /* }}} int apply */ - static int rate_network (const sn_network_t *n) /* {{{ */ { int rate; - int i; - rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n); - for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) - { - sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i); - rate += SN_STAGE_COMP_NUM (s); - } + rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n) + + sn_network_get_comparator_num (n); return (rate); } /* }}} int rate_network */ @@ -210,12 +211,15 @@ static int rate_network (const sn_network_t *n) /* {{{ */ static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */ { sn_network_t *n; + int mask[SN_NETWORK_INPUT_NUM (initial_network)]; + + memcpy (mask, ind, sizeof (mask)); n = sn_network_clone (initial_network); if (n == NULL) return (NULL); - apply (n, ind); + sn_network_cut (n, mask); sn_network_normalize (n); sn_network_compress (n); @@ -240,7 +244,7 @@ static int ind_rate (const void *arg) /* {{{ */ static void *ind_copy (const void *in) /* {{{ */ { - size_t s = sizeof (individuum_t) * cuts_num; + size_t s = sizeof (individuum_t) * inputs_num; void *out; out = malloc (s); @@ -257,77 +261,90 @@ static void ind_free (void *ind) /* {{{ */ free (ind); } /* }}} void ind_free */ -static void ind_print (const individuum_t *ind) +static void ind_print (const individuum_t *ind) /* {{{ */ +{ + int i; + + for (i = 0; i < inputs_num; i++) + { + printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" : + (ind[i] < 0) ? "MIN" : "MAX"); + } + + printf ("# sn-cut"); + for (i = 0; i < inputs_num; i++) + { + if (ind[i] == 0) + continue; + printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX"); + } + printf ("\n"); +} /* }}} void ind_print */ + +/* Simply makes sure the right amount of cutting positions exist. */ +static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */ { int i; - for (i = 0; i < cuts_num; i++) + if (this_cuts_num < 0) { - int input = ind[i]; - int dir = 0; + this_cuts_num = 0; + for (i = 0; i < inputs_num; i++) + if (ind[i] != 0) + this_cuts_num++; + } + + while (this_cuts_num != cuts_num) + { + i = sn_bounded_random (0, inputs_num - 1); - if (input < 0) + if ((this_cuts_num < cuts_num) + && (ind[i] == 0)) { - input *= -1; - dir = 1; + ind[i] = (sn_bounded_random (0, 1) * 2) - 1; + assert (ind[i] != 0); + this_cuts_num++; + } + else if ((this_cuts_num > cuts_num) + && (ind[i] != 0)) + { + ind[i] = 0; + this_cuts_num--; } - input--; - - printf ("%s(%3i)\n", (dir == 0) ? "MAX" : "MIN", input); } -} /* }}} void ind_print */ +} /* }}} void mutate */ static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */ { individuum_t *offspring; - int cut_at; + int this_cuts_num; int i; if ((i0 == NULL) || (i1 == NULL)) return (NULL); - offspring = malloc (sizeof (*offspring) * cuts_num); + offspring = malloc (sizeof (*offspring) * inputs_num); if (offspring == NULL) return (NULL); - memset (offspring, 0, sizeof (*offspring) * cuts_num); + memset (offspring, 0, sizeof (*offspring) * inputs_num); - cut_at = sn_bounded_random (0, cuts_num); - for (i = 0; i < cuts_num; i++) + this_cuts_num = 0; + for (i = 0; i < this_cuts_num; i++) { - if (i < cut_at) + if (sn_bounded_random (0, 1) == 0) offspring[i] = i0[i]; else offspring[i] = i1[i]; + + if (offspring[i] != 0) + this_cuts_num++; } + mutate (offspring, this_cuts_num); + return (offspring); } /* }}} individuum_t *recombine */ -static void random_cut (individuum_t *ind, int index) /* {{{ */ -{ - int max_input = inputs_num - index; - - ind[index] = 0; - while (ind[index] == 0) - ind[index] = sn_bounded_random ((-1) * max_input, max_input); -} /* }}} void random_cut */ - -static void mutate (individuum_t *ind) /* {{{ */ -{ - int reset_input; - int i; - - reset_input = sn_bounded_random (0, 3 * cuts_num); - for (i = 0; i < cuts_num; i++) - { - if (reset_input == i) - random_cut (ind, i); - - if (sn_bounded_random (0, 100)) - ind[i] *= (-1); - } -} /* }}} void mutate */ - static int create_offspring (void) /* {{{ */ { individuum_t *i0; @@ -338,7 +355,6 @@ static int create_offspring (void) /* {{{ */ i1 = population_get_random (population); i2 = recombine (i0, i1); - mutate (i2); population_insert (population, i2); @@ -418,7 +434,13 @@ static int evolution_start (int threads_num) /* {{{ */ printf ("Best after approximately %i iterations: " "%i comparators in %i stages. Rating: %i.\n", iter, comparators_num, stages_num, rating); + + if ((target_rating > 0) && (rating <= target_rating)) + do_loop++; } + + if ((max_iterations > 0) && (iteration_counter >= max_iterations)) + do_loop++; } for (i = 0; i < threads_num; i++) @@ -489,17 +511,14 @@ int main (int argc, char **argv) /* {{{ */ for (i = 0; i < max_population_size; i++) { /* create a random initial individuum */ individuum_t *ind; - int i; - ind = malloc (sizeof (*ind) * cuts_num); + ind = calloc (inputs_num, sizeof (*ind)); if (ind == NULL) { - fprintf (stderr, "malloc failed.\n"); + fprintf (stderr, "calloc failed.\n"); exit (EXIT_FAILURE); } - - for (i = 0; i < cuts_num; i++) - random_cut (ind, i); + mutate (ind, /* num cuts = */ 0); population_insert (population, ind); ind_free (ind);