X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fmath%2Fcategoricals.c;h=d8606031c943b0925a1edc953e454693a9d8de8c;hb=bc9098242e54d481b2c5e2cef970568ab5e953cb;hp=6e39ff2682c45b0bb7c638189d9fe6042711b8a8;hpb=d725a9fcccd8c826cda4278294419024d04efc90;p=pspp diff --git a/src/math/categoricals.c b/src/math/categoricals.c index 6e39ff2682..d8606031c9 100644 --- a/src/math/categoricals.c +++ b/src/math/categoricals.c @@ -32,22 +32,24 @@ #include "gl/xalloc.h" +#define EFFECTS_CODING 1 + struct value_node { struct hmap_node node; /* Node in hash map. */ union value val; /* The value */ + int index; /* A zero based unique index for this value */ }; struct interaction_value { - struct hmap_node node; /* Node in hash map. */ + struct hmap_node node; /* Node in hash map */ - struct ccase *ccase; /* A case (probably the first in the dataset) which matches this value */ + struct ccase *ccase; /* A case (probably the first in the dataset) which matches this value */ - /* Total of the weights of cases matching this interaction */ - double cc; + double cc; /* Total of the weights of cases matching this interaction */ void *user_data; /* A pointer to data which the caller can store stuff */ }; @@ -71,8 +73,10 @@ struct variable_node const struct variable *var; /* The variable */ struct hmap valmap; /* A map of value nodes */ + int n_vals; /* Number of values for this variable */ }; +#if 0 static void dump_interaction (const struct interaction *iact) { @@ -81,6 +85,7 @@ dump_interaction (const struct interaction *iact) printf ("Interaction: %s\n", ds_cstr (&str)); ds_destroy (&str); } +#endif static struct variable_node * @@ -112,8 +117,12 @@ struct interact_params /* The number of distinct values of this interaction */ int n_cats; - /* The degrees of freedom for this interaction */ - int df; + /* An array of integers df_n * df_{n-1} * df_{n-2} ... + These are the products of the degrees of freedom for the current + variable and all preceeding variables */ + int *df_prod; + + double *enc_sum; /* A map of interaction_values indexed by subscript */ struct interaction_value **reverse_interaction_value_map; @@ -180,7 +189,7 @@ struct categoricals void *aux2; }; - +#if 0 static void categoricals_dump (const struct categoricals *cat) { @@ -238,11 +247,39 @@ categoricals_dump (const struct categoricals *cat) printf (")\n"); } } - +#endif void categoricals_destroy (struct categoricals *cat) { + struct variable_node *vn = NULL; + int i; + if (NULL == cat) + return; + for (i = 0; i < cat->n_iap; ++i) + { + struct interaction_value *iv = NULL; + /* Interate over each interaction value, and unref any cases that we reffed */ + HMAP_FOR_EACH (iv, struct interaction_value, node, &cat->iap[i].ivmap) + { + case_unref (iv->ccase); + } + + free (cat->iap[i].enc_sum); + free (cat->iap[i].df_prod); + hmap_destroy (&cat->iap[i].ivmap); + } + + /* Interate over each variable and delete its value map */ + HMAP_FOR_EACH (vn, struct variable_node, node, &cat->varmap) + { + hmap_destroy (&vn->valmap); + } + + hmap_destroy (&cat->varmap); + + pool_destroy (cat->pool); + free (cat); } @@ -252,7 +289,7 @@ static struct interaction_value * lookup_case (const struct hmap *map, const struct interaction *iact, const struct ccase *c) { struct interaction_value *iv = NULL; - size_t hash = interaction_case_hash (iact, c); + size_t hash = interaction_case_hash (iact, c, 0); HMAP_FOR_EACH_WITH_HASH (iv, struct interaction_value, node, hash, map) { @@ -308,6 +345,7 @@ categoricals_create (struct interaction *const*inter, size_t n_inter, { vn = pool_malloc (cat->pool, sizeof *vn); vn->var = var; + vn->n_vals = 0; hmap_init (&vn->valmap); hmap_insert (&cat->varmap, &vn->node, hash); @@ -342,13 +380,13 @@ categoricals_update (struct categoricals *cat, const struct ccase *c) if (valn == NULL) { valn = pool_malloc (cat->pool, sizeof *valn); + valn->index = vn->n_vals++; value_init (&valn->val, width); value_copy (&valn->val, val, width); hmap_insert (&vn->valmap, &valn->node, hash); } } - for (i = 0 ; i < cat->n_iap; ++i) { const struct interaction *iact = cat->iap[i].iact; @@ -356,7 +394,7 @@ categoricals_update (struct categoricals *cat, const struct ccase *c) // if ( interaction_case_is_missing (iact, c, cat->exclude)) // continue; - size_t hash = interaction_case_hash (iact, c); + size_t hash = interaction_case_hash (iact, c, 0); struct interaction_value *node = lookup_case (&cat->iap[i].ivmap, iact, c); if ( NULL == node) @@ -393,7 +431,8 @@ categoricals_n_count (const struct categoricals *cat, size_t n) size_t categoricals_df (const struct categoricals *cat, size_t n) { - return cat->iap[n].df; + const struct interact_params *iap = &cat->iap[n]; + return iap->df_prod[iap->iact->n_vars - 1]; } @@ -401,7 +440,8 @@ categoricals_df (const struct categoricals *cat, size_t n) size_t categoricals_n_total (const struct categoricals *cat) { - assert (cat->reverse_variable_map_long); + if (!categoricals_is_complete (cat)) + return 0; return cat->n_cats_total; } @@ -412,9 +452,16 @@ categoricals_df_total (const struct categoricals *cat) return cat->df_sum; } +bool +categoricals_is_complete (const struct categoricals *cat) +{ + return (NULL != cat->reverse_variable_map_short); +} + + /* This function must be called *before* any call to categoricals_get_*_by subscript and *after* all calls to categoricals_update */ -void +bool categoricals_done (const struct categoricals *cat_) { /* Implementation Note: Whilst this function is O(n) in cat->n_cats_total, in most @@ -434,22 +481,29 @@ categoricals_done (const struct categoricals *cat_) /* Calculate the degrees of freedom, and the number of categories */ for (i = 0 ; i < cat->n_iap; ++i) { + int df = 1; const struct interaction *iact = cat->iap[i].iact; - cat->iap[i].df = 1; - cat->iap[i].n_cats = 1; + cat->iap[i].df_prod = xcalloc (iact->n_vars, sizeof (int)); + cat->iap[i].n_cats = 1; + for (v = 0 ; v < iact->n_vars; ++v) { const struct variable *var = iact->vars[v]; struct variable_node *vn = lookup_variable (&cat->varmap, var, hash_pointer (var, 0)); - cat->iap[i].df *= hmap_count (&vn->valmap) - 1; + if (hmap_count (&vn->valmap) == 0) + return false; + + cat->iap[i].df_prod[v] = df * (hmap_count (&vn->valmap) - 1); + df = cat->iap[i].df_prod[v]; + cat->iap[i].n_cats *= hmap_count (&vn->valmap); } - cat->df_sum += cat->iap[i].df; + cat->df_sum += cat->iap[i].df_prod [v - 1]; cat->n_cats_total += cat->iap[i].n_cats; } @@ -486,8 +540,12 @@ categoricals_done (const struct categoricals *cat_) sort (iap->reverse_interaction_value_map, x, sizeof (*iap->reverse_interaction_value_map), compare_interaction_value_3way, iap); + /* Fill the remaining values with null */ + for (ii = x ; ii < iap->n_cats; ++ii) + iap->reverse_interaction_value_map[ii] = NULL; + /* Populate the reverse variable maps. */ - for (ii = 0; ii < iap->df; ++ii) + for (ii = 0; ii < iap->df_prod [iap->iact->n_vars - 1]; ++ii) cat->reverse_variable_map_short[idx_short++] = i; for (ii = 0; ii < iap->n_cats; ++ii) @@ -497,6 +555,30 @@ categoricals_done (const struct categoricals *cat_) assert (cat->n_vars <= cat->n_iap); // categoricals_dump (cat); + + /* Tally up the sums for all the encodings */ + for (i = 0 ; i < cat->n_iap; ++i) + { + int x, y; + struct interact_params *iap = &cat->iap[i]; + const struct interaction *iact = iap->iact; + + const int df = iap->df_prod [iact->n_vars - 1]; + + iap->enc_sum = xcalloc (df, sizeof (*(iap->enc_sum))); + + for (y = 0; y < hmap_count (&iap->ivmap); ++y) + { + struct interaction_value *iv = iap->reverse_interaction_value_map[y]; + for (x = iap->base_subscript_short; x < iap->base_subscript_short + df ;++x) + { + const double bin = categoricals_get_code_for_case (cat, x, iv->ccase); \ + iap->enc_sum [x - iap->base_subscript_short] += bin * iv->cc; + } + } + } + + return true; } @@ -530,18 +612,6 @@ categoricals_get_interaction_by_subscript (const struct categoricals *cat, int s return cat->iap[index].iact; } - -/* Return the case corresponding to SUBSCRIPT */ -static const struct ccase * -categoricals_get_case_by_subscript (const struct categoricals *cat, int subscript) -{ - int vindex = reverse_variable_lookup_short (cat, subscript); - const struct interact_params *vp = &cat->iap[vindex]; - const struct interaction_value *vn = vp->reverse_interaction_value_map [subscript - vp->base_subscript_short]; - return vn->ccase; -} - - double categoricals_get_weight_by_subscript (const struct categoricals *cat, int subscript) { @@ -557,22 +627,58 @@ categoricals_get_sum_by_subscript (const struct categoricals *cat, int subscript int vindex = reverse_variable_lookup_short (cat, subscript); const struct interact_params *vp = &cat->iap[vindex]; - const struct interaction_value *iv = vp->reverse_interaction_value_map [subscript - vp->base_subscript_short]; - - return iv->cc; + return vp->enc_sum[subscript - vp->base_subscript_short]; } /* Returns unity if the value in case C at SUBSCRIPT is equal to the category for that subscript */ double -categoricals_get_binary_by_subscript (const struct categoricals *cat, int subscript, +categoricals_get_code_for_case (const struct categoricals *cat, int subscript, const struct ccase *c) { const struct interaction *iact = categoricals_get_interaction_by_subscript (cat, subscript); - const struct ccase *c2 = categoricals_get_case_by_subscript (cat, subscript); + const int i = reverse_variable_lookup_short (cat, subscript); + + const int base_index = cat->iap[i].base_subscript_short; + + int v; + double result = 1.0; + + const struct interact_params *iap = &cat->iap[i]; + + double dfp = 1.0; + for (v = 0; v < iact->n_vars; ++v) + { + const struct variable *var = iact->vars[v]; + + const union value *val = case_data (c, var); + const int width = var_get_width (var); + const struct variable_node *vn = lookup_variable (&cat->varmap, var, hash_pointer (var, 0)); + + const unsigned int hash = value_hash (val, width, 0); + const struct value_node *valn = lookup_value (&vn->valmap, val, hash, width); - return interaction_case_equal (iact, c, c2); + double bin = 1.0; + + const double df = iap->df_prod[v] / dfp; + + /* Translate the subscript into an index for the individual variable */ + const int index = ((subscript - base_index) % iap->df_prod[v] ) / dfp; + dfp = iap->df_prod [v]; + +#if EFFECTS_CODING + if ( valn->index == df ) + bin = -1.0; + else +#endif + if ( valn->index != index ) + bin = 0; + + result *= bin; + } + + return result; } @@ -603,3 +709,7 @@ categoricals_get_user_data_by_category (const struct categoricals *cat, int subs const struct interaction_value *iv = vp->reverse_interaction_value_map [subscript - vp->base_subscript_long]; return iv->user_data; } + + + +