X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flanguage%2Fstats%2Fchisquare.c;h=10d81132715552b7ccaad1d96ad2587cf20988ac;hb=2be9bee9da6a2ce27715e58128569594319abfa2;hp=6b0b0567257bd80d5b812a96438464e8fc4bf75f;hpb=43b1296aafe7582e7dbe6c2b6a8b478d7d9b0fcf;p=pspp-builds.git diff --git a/src/language/stats/chisquare.c b/src/language/stats/chisquare.c index 6b0b0567..10d81132 100644 --- a/src/language/stats/chisquare.c +++ b/src/language/stats/chisquare.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 2006, 2007 Free Software Foundation, Inc. + Copyright (C) 2006, 2007, 2009, 2010, 2011 Free Software Foundation, Inc. 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 @@ -16,163 +16,118 @@ #include -#include +#include "language/stats/chisquare.h" -#include +#include #include +#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include +#include "data/case.h" +#include "data/casereader.h" +#include "data/dataset.h" +#include "data/dictionary.h" +#include "data/format.h" +#include "data/value-labels.h" +#include "data/variable.h" +#include "language/stats/freq.h" +#include "language/stats/npar.h" +#include "libpspp/array.h" +#include "libpspp/assertion.h" +#include "libpspp/cast.h" +#include "libpspp/compiler.h" +#include "libpspp/hash-functions.h" +#include "libpspp/message.h" +#include "libpspp/taint.h" +#include "output/tab.h" + +#include "gl/xalloc.h" #include "gettext.h" #define _(msgid) gettext (msgid) -/* Return a hash table containing the frequency counts of each - value of VAR in CF . - It is the caller's responsibility to free the hash table when - no longer required. -*/ -static struct hsh_table * +/* Adds frequency counts of each value of VAR in INPUT between LO and HI to + FREQ_HASH. LO and HI and each input value is truncated to an integer. + Returns true if successful, false on input error. It is the caller's + responsibility to initialize FREQ_HASH and to free it when no longer + required, even on failure. */ +static bool create_freq_hash_with_range (const struct dictionary *dict, struct casereader *input, const struct variable *var, - double lo, - double hi) + double lo_, double hi_, + struct hmap *freq_hash) { + struct freq **entries; bool warn = true; - float i_d; - struct ccase c; + struct ccase *c; + double lo, hi; + double i_d; - struct hsh_table *freq_hash = - hsh_create (4, compare_freq, hash_freq, - free_freq_mutable_hash, - (void *) var); + assert (var_is_numeric (var)); + lo = trunc (lo_); + hi = trunc (hi_); /* Populate the hash with zero entries */ - for (i_d = trunc (lo); i_d <= trunc (hi); i_d += 1.0 ) + entries = xnmalloc (hi - lo + 1, sizeof *entries); + for (i_d = lo; i_d <= hi; i_d += 1.0 ) { - union value the_value; - struct freq_mutable *fr = xmalloc (sizeof (*fr)); - - the_value.f = i_d; - - fr->value = value_dup (&the_value, 0); - fr->count = 0; - - hsh_insert (freq_hash, fr); + size_t ofs = i_d - lo; + union value value = { i_d }; + entries[ofs] = freq_hmap_insert (freq_hash, &value, 0, + value_hash (&value, 0, 0)); } - while (casereader_read (input, &c)) + for (; (c = casereader_read (input)) != NULL; case_unref (c)) { - union value obs_value; - struct freq **existing_fr; - struct freq *fr = xmalloc(sizeof (*fr)); - fr->value = case_data (&c, var); - - fr->count = dict_get_case_weight (dict, &c, &warn); - - obs_value.f = trunc (fr->value->f); - - if ( obs_value.f < lo || obs_value.f > hi) - { - free (fr); - case_destroy (&c); - continue; - } - - fr->value = &obs_value; - - existing_fr = (struct freq **) hsh_probe (freq_hash, fr); - - /* This must exist in the hash, because we previously populated it - with zero counts */ - assert (*existing_fr); - - (*existing_fr)->count += fr->count; - free (fr); - - case_destroy (&c); - } - if (casereader_destroy (input)) - return freq_hash; - else - { - hsh_destroy (freq_hash); - return NULL; + double x = trunc (case_num (c, var)); + if (x >= lo && x <= hi) + { + size_t ofs = x - lo; + struct freq *fr = entries[ofs]; + fr->count += dict_get_case_weight (dict, c, &warn); + } } -} + return casereader_destroy (input); +} -/* Return a hash table containing the frequency counts of each - value of VAR in INPUT . - It is the caller's responsibility to free the hash table when - no longer required. -*/ -static struct hsh_table * +/* Adds frequency counts of each value of VAR in INPUT to FREQ_HASH. LO and HI + and each input value is truncated to an integer. Returns true if + successful, false on input error. It is the caller's responsibility to + initialize FREQ_HASH and to free it when no longer required, even on + failure. */ +static bool create_freq_hash (const struct dictionary *dict, struct casereader *input, - const struct variable *var) + const struct variable *var, + struct hmap *freq_hash) { + int width = var_get_width (var); bool warn = true; - struct ccase c; - - struct hsh_table *freq_hash = - hsh_create (4, compare_freq, hash_freq, - free_freq_mutable_hash, - (void *) var); + struct ccase *c; - for (; casereader_read (input, &c); case_destroy (&c)) + for (; (c = casereader_read (input)) != NULL; case_unref (c)) { - struct freq **existing_fr; - struct freq *fr = xmalloc(sizeof (*fr)); - fr->value = case_data (&c, var); + const union value *value = case_data (c, var); + size_t hash = value_hash (value, width, 0); + double weight = dict_get_case_weight (dict, c, &warn); + struct freq *f; - fr->count = dict_get_case_weight (dict, &c, &warn); + f = freq_hmap_search (freq_hash, value, width, hash); + if (f == NULL) + f = freq_hmap_insert (freq_hash, value, width, hash); - existing_fr = (struct freq **) hsh_probe (freq_hash, fr); - if ( *existing_fr) - { - (*existing_fr)->count += fr->count; - free (fr); - } - else - { - *existing_fr = fr; - fr->value = value_dup (fr->value, var_get_width (var)); - } + f->count += weight; } - if (casereader_destroy (input)) - return freq_hash; - else - { - hsh_destroy (freq_hash); - return NULL; - } -} - + return casereader_destroy (input); +} static struct tab_table * create_variable_frequency_table (const struct dictionary *dict, struct casereader *input, const struct chisquare_test *test, - int v, - struct hsh_table **freq_hash) + int v, struct hmap *freq_hash) { int i; @@ -181,11 +136,14 @@ create_variable_frequency_table (const struct dictionary *dict, struct tab_table *table ; const struct variable *var = ost->vars[v]; - *freq_hash = create_freq_hash (dict, input, var); - if (*freq_hash == NULL) - return NULL; + hmap_init (freq_hash); + if (!create_freq_hash (dict, input, var, freq_hash)) + { + freq_hmap_destroy (freq_hash, var_get_width (var)); + return NULL; + } - n_cells = hsh_count (*freq_hash); + n_cells = hmap_count (freq_hash); if ( test->n_expected > 0 && n_cells != test->n_expected ) { @@ -197,10 +155,9 @@ create_variable_frequency_table (const struct dictionary *dict, return NULL; } - table = tab_create(4, n_cells + 2, 0); - tab_dim (table, tab_natural_dimensions); + table = tab_create(4, n_cells + 2); - tab_title (table, var_to_string(var)); + tab_title (table, "%s", var_to_string(var)); tab_text (table, 1, 0, TAB_LEFT, _("Observed N")); tab_text (table, 2, 0, TAB_LEFT, _("Expected N")); tab_text (table, 3, 0, TAB_LEFT, _("Residual")); @@ -208,7 +165,7 @@ create_variable_frequency_table (const struct dictionary *dict, tab_headers (table, 1, 0, 1, 0); tab_box (table, TAL_1, TAL_1, -1, -1, - 0, 0, table->nc - 1, tab_nr(table) - 1 ); + 0, 0, tab_nc (table) - 1, tab_nr(table) - 1 ); tab_hline (table, TAL_1, 0, tab_nc(table) - 1, 1); @@ -217,7 +174,7 @@ create_variable_frequency_table (const struct dictionary *dict, tab_vline (table, TAL_1, i, 0, tab_nr(table) - 1); - tab_text (table, 0, table->nr - 1, TAB_LEFT, _("Total")); + tab_text (table, 0, tab_nr (table) - 1, TAB_LEFT, _("Total")); return table; } @@ -233,8 +190,7 @@ create_combo_frequency_table (const struct chisquare_test *test) int n_cells = test->hi - test->lo + 1; - table = tab_create(1 + ost->n_vars * 4, n_cells + 3, 0); - tab_dim (table, tab_natural_dimensions); + table = tab_create(1 + ost->n_vars * 4, n_cells + 3); tab_title (table, _("Frequencies")); for ( i = 0 ; i < ost->n_vars ; ++i ) @@ -266,18 +222,18 @@ create_combo_frequency_table (const struct chisquare_test *test) } for ( i = test->lo ; i <= test->hi ; ++i ) - tab_float (table, 0, 2 + i - test->lo, - TAB_LEFT, 1 + i - test->lo, 8, 0); + tab_fixed (table, 0, 2 + i - test->lo, + TAB_LEFT, 1 + i - test->lo, 8, 0); tab_headers (table, 1, 0, 2, 0); tab_box (table, TAL_1, TAL_1, -1, -1, - 0, 0, table->nc - 1, tab_nr(table) - 1 ); + 0, 0, tab_nc (table) - 1, tab_nr(table) - 1 ); tab_hline (table, TAL_1, 1, tab_nc(table) - 1, 1); tab_hline (table, TAL_1, 0, tab_nc(table) - 1, 2); - tab_text (table, 0, table->nr - 1, TAB_LEFT, _("Total")); + tab_text (table, 0, tab_nr (table) - 1, TAB_LEFT, _("Total")); return table; } @@ -289,8 +245,7 @@ create_stats_table (const struct chisquare_test *test) const struct one_sample_test *ost = (const struct one_sample_test*) test; struct tab_table *table; - table = tab_create (1 + ost->n_vars, 4, 0); - tab_dim (table, tab_natural_dimensions); + table = tab_create (1 + ost->n_vars, 4); tab_title (table, _("Test Statistics")); tab_headers (table, 1, 0, 1, 0); @@ -317,14 +272,20 @@ void chisquare_execute (const struct dataset *ds, struct casereader *input, enum mv_class exclude, - const struct npar_test *test) + const struct npar_test *test, + bool exact UNUSED, + double timer UNUSED) { const struct dictionary *dict = dataset_dict (ds); int v, i; - struct one_sample_test *ost = (struct one_sample_test *) test; - struct chisquare_test *cst = (struct chisquare_test *) test; + struct chisquare_test *cst = UP_CAST (test, struct chisquare_test, + parent.parent); + struct one_sample_test *ost = &cst->parent; int n_cells = 0; double total_expected = 0.0; + const struct variable *wvar = dict_get_weight (dict); + const struct fmt_spec *wfmt = wvar ? + var_get_print_format (wvar) : & F_8_0; double *df = xzalloc (sizeof (*df) * ost->n_vars); double *xsq = xzalloc (sizeof (*df) * ost->n_vars); @@ -337,11 +298,13 @@ chisquare_execute (const struct dataset *ds, { for ( v = 0 ; v < ost->n_vars ; ++v ) { + const struct variable *var = ost->vars[v]; double total_obs = 0.0; - struct hsh_table *freq_hash = NULL; + struct hmap freq_hash; struct casereader *reader = casereader_create_filter_missing (casereader_clone (input), - &ost->vars[v], 1, exclude, NULL); + &var, 1, exclude, + NULL, NULL); struct tab_table *freq_table = create_variable_frequency_table(dict, reader, cst, v, &freq_hash); @@ -349,9 +312,9 @@ chisquare_execute (const struct dataset *ds, if ( NULL == freq_table ) continue; - ff = (struct freq **) hsh_sort (freq_hash); + ff = freq_hmap_sort (&freq_hash, var_get_width (var)); - n_cells = hsh_count (freq_hash); + n_cells = hmap_count (&freq_hash); for ( i = 0 ; i < n_cells ; ++i ) total_obs += ff[i]->count; @@ -359,40 +322,46 @@ chisquare_execute (const struct dataset *ds, xsq[v] = 0.0; for ( i = 0 ; i < n_cells ; ++i ) { + struct string str; double exp; - const union value *observed_value = ff[i]->value; + const union value *observed_value = &ff[i]->value; + + ds_init_empty (&str); + var_append_value_name (var, observed_value, &str); /* The key */ - tab_text (freq_table, 0, i + 1, TAB_LEFT, - var_get_value_name (ost->vars[v], observed_value)); + tab_text (freq_table, 0, i + 1, TAB_LEFT, ds_cstr (&str)); + ds_destroy (&str); + /* The observed N */ - tab_float (freq_table, 1, i + 1, TAB_NONE, - ff[i]->count, 8, 0); + tab_double (freq_table, 1, i + 1, TAB_NONE, + ff[i]->count, wfmt); if ( cst->n_expected > 0 ) exp = cst->expected[i] * total_obs / total_expected ; else exp = total_obs / (double) n_cells; - tab_float (freq_table, 2, i + 1, TAB_NONE, - exp, 8, 2); + tab_double (freq_table, 2, i + 1, TAB_NONE, + exp, NULL); /* The residual */ - tab_float (freq_table, 3, i + 1, TAB_NONE, - ff[i]->count - exp, 8, 2); + tab_double (freq_table, 3, i + 1, TAB_NONE, + ff[i]->count - exp, NULL); xsq[v] += (ff[i]->count - exp) * (ff[i]->count - exp) / exp; } df[v] = n_cells - 1.0; - tab_float (freq_table, 1, i + 1, TAB_NONE, - total_obs, 8, 0); + tab_double (freq_table, 1, i + 1, TAB_NONE, + total_obs, wfmt); tab_submit (freq_table); - hsh_destroy (freq_hash); + freq_hmap_destroy (&freq_hash, var_get_width (var)); + free (ff); } } else /* ranged == true */ @@ -403,63 +372,71 @@ chisquare_execute (const struct dataset *ds, for ( v = 0 ; v < ost->n_vars ; ++v ) { + const struct variable *var = ost->vars[v]; double total_obs = 0.0; struct casereader *reader = casereader_create_filter_missing (casereader_clone (input), - &ost->vars[v], 1, exclude, NULL); - struct hsh_table *freq_hash = - create_freq_hash_with_range (dict, reader, - ost->vars[v], cst->lo, cst->hi); - + &var, 1, exclude, + NULL, NULL); + struct hmap freq_hash; struct freq **ff; - if (freq_hash == NULL) - continue; + hmap_init (&freq_hash); + if (!create_freq_hash_with_range (dict, reader, var, + cst->lo, cst->hi, &freq_hash)) + { + freq_hmap_destroy (&freq_hash, var_get_width (var)); + continue; + } - ff = (struct freq **) hsh_sort (freq_hash); - assert ( n_cells == hsh_count (freq_hash)); + ff = freq_hmap_sort (&freq_hash, var_get_width (var)); - for ( i = 0 ; i < hsh_count (freq_hash) ; ++i ) + for ( i = 0 ; i < hmap_count (&freq_hash) ; ++i ) total_obs += ff[i]->count; xsq[v] = 0.0; - for ( i = 0 ; i < hsh_count (freq_hash) ; ++i ) + for ( i = 0 ; i < hmap_count (&freq_hash) ; ++i ) { + struct string str; double exp; - const union value *observed_value = ff[i]->value; + const union value *observed_value = &ff[i]->value; + ds_init_empty (&str); + var_append_value_name (ost->vars[v], observed_value, &str); /* The key */ tab_text (freq_table, v * 4 + 1, i + 2 , TAB_LEFT, - var_get_value_name (ost->vars[v], observed_value)); + ds_cstr (&str)); + ds_destroy (&str); /* The observed N */ - tab_float (freq_table, v * 4 + 2, i + 2 , TAB_NONE, - ff[i]->count, 8, 0); + tab_double (freq_table, v * 4 + 2, i + 2 , TAB_NONE, + ff[i]->count, wfmt); if ( cst->n_expected > 0 ) exp = cst->expected[i] * total_obs / total_expected ; else - exp = total_obs / (double) hsh_count (freq_hash); + exp = total_obs / (double) hmap_count (&freq_hash); /* The expected N */ - tab_float (freq_table, v * 4 + 3, i + 2 , TAB_NONE, - exp, 8, 2); + tab_double (freq_table, v * 4 + 3, i + 2 , TAB_NONE, + exp, NULL); /* The residual */ - tab_float (freq_table, v * 4 + 4, i + 2 , TAB_NONE, - ff[i]->count - exp, 8, 2); + tab_double (freq_table, v * 4 + 4, i + 2 , TAB_NONE, + ff[i]->count - exp, NULL); xsq[v] += (ff[i]->count - exp) * (ff[i]->count - exp) / exp; } - tab_float (freq_table, v * 4 + 2, tab_nr (freq_table) - 1, TAB_NONE, - total_obs, 8, 0); + tab_double (freq_table, v * 4 + 2, tab_nr (freq_table) - 1, TAB_NONE, + total_obs, wfmt); df[v] = n_cells - 1.0; - hsh_destroy (freq_hash); + freq_hmap_destroy (&freq_hash, var_get_width (var)); + free (ff); } tab_submit (freq_table); @@ -478,11 +455,11 @@ chisquare_execute (const struct dataset *ds, tab_text (stats_table, 1 + v, 0, TAB_CENTER, var_get_name (var)); - tab_float (stats_table, 1 + v, 1, TAB_NONE, xsq[v], 8,3); - tab_float (stats_table, 1 + v, 2, TAB_NONE, df[v], 8,0); + tab_double (stats_table, 1 + v, 1, TAB_NONE, xsq[v], NULL); + tab_fixed (stats_table, 1 + v, 2, TAB_NONE, df[v], 8, 0); - tab_float (stats_table, 1 + v, 3, TAB_NONE, - gsl_cdf_chisq_Q (xsq[v], df[v]), 8,3); + tab_double (stats_table, 1 + v, 3, TAB_NONE, + gsl_cdf_chisq_Q (xsq[v], df[v]), NULL); } tab_submit (stats_table); }