From 25d4accd732b929388c2cde4476b2c077ae1d235 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 4 Feb 2011 14:08:24 +0100 Subject: [PATCH] sn-markov: Implement counting of comparators. --- src/Makefile.am | 3 +- src/histogram.c | 168 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/histogram.h | 34 ++++++++++++ src/sn-markov.c | 11 ++++ 4 files changed, 215 insertions(+), 1 deletion(-) create mode 100644 src/histogram.c create mode 100644 src/histogram.h diff --git a/src/Makefile.am b/src/Makefile.am index 6d579fd..09a9959 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -49,7 +49,8 @@ sn_cut_LDADD = libsortnetwork.la sn_info_SOURCES = sn-info.c sn_info_LDADD = libsortnetwork.la -sn_markov_SOURCES = sn-markov.c +sn_markov_SOURCES = sn-markov.c \ + histogram.c histogram.h sn_markov_LDADD = libsortnetwork.la sn_merge_SOURCES = sn-merge.c diff --git a/src/histogram.c b/src/histogram.c new file mode 100644 index 0000000..db6a4d9 --- /dev/null +++ b/src/histogram.c @@ -0,0 +1,168 @@ +/** + * libsortnetwork - src/histrogram.c + * Copyright (C) 2011 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 + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200809L +#endif +#ifndef _XOPEN_SOURCE +# define _XOPEN_SOURCE 700 +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include "histogram.h" + +#define BAR_WIDTH 64 + +struct histogram_s +{ + uint64_t *data; + int index_min; + int index_max; +}; + +static int hist_resize (histogram_t *h, int rating) /* {{{ */ +{ + int min_new; + int max_new; + size_t nelem_new; + size_t nelem_old; + uint64_t *tmp; + + if ((h->index_min == 0) && (h->index_max == 0)) + { + min_new = rating; + max_new = rating; + } + else + { + min_new = ((h->index_min < rating) ? h->index_min : rating); + max_new = ((h->index_max > rating) ? h->index_max : rating); + } + + nelem_new = (size_t) ((max_new - min_new) + 1); + nelem_old = (size_t) ((h->index_max - h->index_min) + 1); + + assert (nelem_new >= nelem_old); + + tmp = realloc (h->data, nelem_new * sizeof (*h->data)); + if (tmp == NULL) + return (ENOMEM); + h->data = tmp; + + if ((h->index_min == 0) && (h->index_max == 0)) + { + h->index_min = min_new; + h->index_max = max_new; + h->data[0] = 0; + return (0); + } + + if (min_new < h->index_min) + { + size_t diff = (size_t) (h->index_min - min_new); + + memmove (h->data + diff, h->data, nelem_old * sizeof (*h->data)); + memset (h->data, 0, diff * sizeof (*h->data)); + + h->index_min = min_new; + } + else if (max_new > h->index_max) + { + size_t diff = (size_t) (max_new - h->index_max); + memset (h->data + nelem_old, 0, diff * sizeof (*h->data)); + + h->index_max = max_new; + } + + return (0); +} /* }}} int hist_resize */ + +histogram_t *hist_create (void) /* {{{ */ +{ + histogram_t *h = malloc (sizeof (*h)); + if (h == NULL) + return (NULL); + memset (h, 0, sizeof (*h)); + h->data = NULL; + + return (h); +} /* }}} hist_create */ + +void hist_destroy (histogram_t *h) /* {{{ */ +{ + if (h != NULL) + free (h->data); + free (h); +} /* }}} hist_destroy */ + +int hist_account (histogram_t *h, int rating) /* {{{ */ +{ + if ((h == NULL) || (rating < 0)) + return (EINVAL); + + if ((rating < h->index_min) || (rating > h->index_max)) + hist_resize (h, rating); + + h->data[rating - h->index_min]++; + + return (0); +} /* }}} int hist_account */ + +int hist_print (histogram_t *h) /* {{{ */ +{ + char bar[BAR_WIDTH + 1]; + uint64_t max; + int i; + + if (h == NULL) + return (EINVAL); + + max = 1; + for (i = h->index_min; i <= h->index_max; i++) + if (max < h->data[i - h->index_min]) + max = h->data[i - h->index_min]; + + for (i = h->index_min; i <= h->index_max; i++) + { + uint64_t num = h->data[i - h->index_min]; + uint64_t points = (BAR_WIDTH * num) / max; + uint64_t j; + + for (j = 0; j < (BAR_WIDTH + 1); j++) + bar[j] = (j < points) ? '#' : 0; + + printf ("%4i: %8"PRIu64" %s\n", i, num, bar); + } + + return (0); +} /* }}} int hist_print */ + +/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */ diff --git a/src/histogram.h b/src/histogram.h new file mode 100644 index 0000000..c52b35c --- /dev/null +++ b/src/histogram.h @@ -0,0 +1,34 @@ +/** + * libsortnetwork - src/histrogram.h + * Copyright (C) 2011 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 + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#ifndef HISTOGRAM_H +#define HISTOGRAM_H 1 + +struct histogram_s; +typedef struct histogram_s histogram_t; + +histogram_t *hist_create (void); +void hist_destroy (histogram_t *h); + +int hist_account (histogram_t *h, int rating); +int hist_print (histogram_t *h); + +#endif /* HISTOGRAM_H */ diff --git a/src/sn-markov.c b/src/sn-markov.c index 1fcc41d..5de4284 100644 --- a/src/sn-markov.c +++ b/src/sn-markov.c @@ -43,6 +43,7 @@ #include "sn_network.h" #include "sn_random.h" +#include "histogram.h" #if !defined(__GNUC__) || !__GNUC__ # define __attribute__(x) /**/ @@ -59,6 +60,8 @@ static int best_rating = INT_MAX; static _Bool do_loop = 1; static uint64_t max_iterations = 0; +static histogram_t *histogram; + static void sigint_handler (int signal __attribute__((unused))) { do_loop = 0; @@ -204,6 +207,8 @@ static void random_walk (sn_network_t *n) best_solution = sn_network_clone (next); } + hist_account (histogram, sn_network_get_comparator_num (next)); + sn_network_destroy (n); n = next; iteration_counter++; @@ -224,6 +229,8 @@ int main (int argc, char **argv) struct sigaction sigint_action; struct sigaction sigterm_action; + histogram = hist_create (); + read_options (argc, argv); if (initial_input_file == NULL) exit_usage (argv[0], EXIT_FAILURE); @@ -254,6 +261,10 @@ int main (int argc, char **argv) random_walk (start_network); start_network = NULL; + hist_print (histogram); + hist_destroy (histogram); + histogram = NULL; + if (best_solution != NULL) { if (best_output_file != NULL) -- 2.11.0