X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn-evolution.c;h=9f63506a6992dc94fad4a9225c47baed4716fb2a;hp=3c11adb61b057441c5ae2ae657cae6ba26273ff0;hb=7113bfbc96eb65431bad9d9985ba04a18f4912cb;hpb=6afcf3afbef32c7f16b12872b5aabcd7a6467786 diff --git a/src/sn-evolution.c b/src/sn-evolution.c index 3c11adb..9f63506 100644 --- a/src/sn-evolution.c +++ b/src/sn-evolution.c @@ -1,6 +1,6 @@ /** - * collectd - src/sn-evolution.c - * Copyright (C) 2008 Florian octo Forster + * libsortnetwork - src/sn-evolution.c + * Copyright (C) 2008-2010 Florian octo Forster * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the @@ -16,20 +16,24 @@ * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * * Authors: - * Florian octo Forster + * Florian octo Forster **/ #ifndef _ISOC99_SOURCE # define _ISOC99_SOURCE #endif #ifndef _POSIX_C_SOURCE -# define _POSIX_C_SOURCE 200112L +# define _POSIX_C_SOURCE 200809L +#endif +#ifndef _XOPEN_SOURCE +# define _XOPEN_SOURCE 700 #endif #include #include #include #include +#include #include #include @@ -46,12 +50,13 @@ #include "sn_network.h" #include "sn_random.h" -/* Yes, this is ugly, but the GNU libc doesn't export it with the above flags. - * */ -char *strdup (const char *s); +#if !defined(__GNUC__) || !__GNUC__ +# define __attribute__(x) /**/ +#endif static uint64_t iteration_counter = 0; static int inputs_num = 16; +static int inputs_num_is_power_of_two = 1; static char *initial_input_file = NULL; static char *best_output_file = NULL; @@ -61,11 +66,18 @@ static int stats_interval = 0; static int max_population_size = 128; static population_t *population; +static enum +{ + MERGER_ODDEVEN, + MERGER_BITONIC, + MERGER_RANDOM +} selected_merger = MERGER_ODDEVEN; + static int evolution_threads_num = 4; static int do_loop = 0; -static void sigint_handler (int signal) +static void sigint_handler (int signal __attribute__((unused))) { do_loop++; } /* void sigint_handler */ @@ -80,6 +92,8 @@ 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" + " -m Specify the merging network to use.\n" + " Available: \"oddeven\", \"bitonic\", \"random\"\n" "\n", name); exit (1); @@ -89,7 +103,7 @@ int read_options (int argc, char **argv) { int option; - while ((option = getopt (argc, argv, "i:o:p:P:s:t:h")) != -1) + while ((option = getopt (argc, argv, "i:o:p:P:s:t:m:h")) != -1) { switch (option) { @@ -149,6 +163,19 @@ int read_options (int argc, char **argv) break; } + case 'm': + { + if (strcasecmp ("oddeven", optarg) == 0) + selected_merger = MERGER_ODDEVEN; + else if (strcasecmp ("bitonic", optarg) == 0) + selected_merger = MERGER_BITONIC; + else if (strcasecmp ("random", optarg) == 0) + selected_merger = MERGER_RANDOM; + else + fprintf (stderr, "Not a valid merging strategy: \"%s\"\n", optarg); + break; + } + case 'h': default: exit_usage (argv[0]); @@ -173,6 +200,7 @@ static int rate_network (const sn_network_t *n) return (rate); } /* int rate_network */ +#if 0 static int mutate_network (sn_network_t *n) { sn_network_t *n_copy; @@ -210,6 +238,7 @@ static int mutate_network (sn_network_t *n) return (0); } /* int mutate_network */ +#endif static int create_offspring (void) { @@ -224,7 +253,12 @@ static int create_offspring (void) assert (p1 != NULL); /* combine the two parents */ - n = sn_network_combine (p0, p1); + if ((selected_merger == MERGER_ODDEVEN) + || ((selected_merger == MERGER_RANDOM) + && (sn_bounded_random (0, 1) == 0))) + n = sn_network_combine_odd_even_merge (p0, p1); + else + n = sn_network_combine_bitonic_merge (p0, p1); sn_network_destroy (p0); sn_network_destroy (p1); @@ -248,8 +282,10 @@ static int create_offspring (void) assert (SN_NETWORK_INPUT_NUM (n) == inputs_num); - if (sn_bounded_random (0, 100) <= 1) +#if 0 + if ((SN_NETWORK_INPUT_NUM (n) <= 16) && (sn_bounded_random (0, 100) <= 1)) mutate_network (n); +#endif population_insert (population, n); @@ -258,7 +294,7 @@ static int create_offspring (void) return (0); } /* int create_offspring */ -static void *evolution_thread (void *arg) +static void *evolution_thread (void *arg __attribute__((unused))) { while (do_loop == 0) { @@ -298,17 +334,32 @@ static int evolution_start (int threads_num) if (status == 0) { sn_network_t *n; + int stages_num; + int comparators_num; int rating; + int iter; - i = iteration_counter; + iter = iteration_counter; n = population_get_fittest (population); + rating = rate_network (n); + + stages_num = SN_NETWORK_STAGE_NUM (n); + comparators_num = 0; + for (i = 0; i < stages_num; i++) + { + sn_stage_t *s; + + s = SN_NETWORK_STAGE_GET (n, i); + comparators_num += SN_STAGE_COMP_NUM (s); + } + sn_network_destroy (n); - printf ("After approximately %i iterations: " - "Currently best rating: %i\n", - i, rating); + printf ("Best after approximately %i iterations: " + "%i comparators in %i stages. Rating: %i.\n", + iter, comparators_num, stages_num, rating); } } @@ -356,6 +407,7 @@ int main (int argc, char **argv) { sn_network_t *n; + int tmp; n = sn_network_read_file (initial_input_file); if (n == NULL) @@ -366,6 +418,23 @@ int main (int argc, char **argv) inputs_num = SN_NETWORK_INPUT_NUM(n); + /* Determine if `inputs_num' is a power of two. If so, more merge + * algorithms can be used. */ + tmp = inputs_num; + inputs_num_is_power_of_two = 1; + while (tmp > 0) + { + if ((tmp % 2) != 0) + { + if (tmp == 1) + inputs_num_is_power_of_two = 1; + else + inputs_num_is_power_of_two = 0; + break; + } + tmp = tmp >> 1; + } + population_insert (population, n); sn_network_destroy (n); }