diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/km-find.c | 28 | ||||
| -rw-r--r-- | src/km-set.c | 7 | ||||
| -rw-r--r-- | src/km-solve.c | 72 | ||||
| -rw-r--r-- | src/km.h | 5 | ||||
| -rw-r--r-- | src/main.c | 4 |
5 files changed, 55 insertions, 61 deletions
diff --git a/src/km-find.c b/src/km-find.c index 5ae5948..e9fed0f 100644 --- a/src/km-find.c +++ b/src/km-find.c @@ -28,9 +28,9 @@ find_solve_on_stats( km_find_data_t * const find_data = cb_data; UNUSED(set); - // save total sum and silouette + // save total sum and silhouette find_data->distance_sum = stats->sum; - find_data->silouette = stats->silouette; + find_data->silhouette = stats->silhouette; } static const km_solve_cbs_t @@ -59,7 +59,14 @@ km_find( return false; } - float best_silouette = -2.0; + // allocate row map: row => distance, cluster ID + km_row_map_t * const row_map = calloc(set->num_rows, sizeof(km_row_map_t)); + if (!row_map) { + // return failure + return false; + } + + float best_silhouette = -2.0; for (size_t i = 2; i < cbs->max_clusters; i++) { for (size_t j = 0; j < cbs->num_tests; j++) { // init cluster set @@ -76,8 +83,8 @@ km_find( }; // solve test - // (populates sum and silouette) - if (!km_solve(&cs, set, &FIND_SOLVE_CBS, &find_data)) { + // (populates sum and silhouette) + if (!km_solve(&cs, set, row_map, &FIND_SOLVE_CBS, &find_data)) { // return failure return false; } @@ -88,15 +95,15 @@ km_find( // emit result cbs->on_data(&find_data, cb_data); - if (find_data.silouette > best_silouette) { + if (find_data.silhouette > best_silhouette) { // emit new best result - if (cbs->on_best && !cbs->on_best(find_data.silouette, &cs, cb_data)) { + if (cbs->on_best && !cbs->on_best(find_data.silhouette, &cs, cb_data)) { // return failure return false; } - // update best silouette - best_silouette = find_data.silouette; + // update best silhouette + best_silhouette = find_data.silhouette; } // finalize cluster set @@ -107,6 +114,9 @@ km_find( } } + // free row map + free(row_map); + // return success return true; } diff --git a/src/km-set.c b/src/km-set.c index fcf1054..ca98a2b 100644 --- a/src/km-set.c +++ b/src/km-set.c @@ -237,6 +237,7 @@ km_set_normalize( } // normalize values + #pragma omp parallel for collapse(2) for (size_t i = 0; i < set->num_rows; i++) { for (size_t j = 0; j < num_floats; j++) { const size_t ofs = i * num_floats + j; @@ -257,21 +258,23 @@ km_set_normalize( } // get row from data set +// unsafe (no bounds checking) float * km_set_get_row( const km_set_t * const set, const size_t i ) { const size_t num_floats = set->shape.num_floats; - return (num_floats) ? (set->floats + i * num_floats) : NULL; + return set->floats + i * num_floats; } // get row from data set +// unsafe (no bounds checking) int * km_set_get_row_ints( const km_set_t * const set, const size_t i ) { const size_t num_ints = set->shape.num_ints; - return (num_ints) ? (set->ints + i * num_ints) : NULL; + return set->ints + i * num_ints; } diff --git a/src/km-solve.c b/src/km-solve.c index b6d98d6..271795b 100644 --- a/src/km-solve.c +++ b/src/km-solve.c @@ -6,36 +6,18 @@ #define MIN_DELTA 0.00001 -// alloc and initialize row map -static km_row_map_t * -km_row_map_init( +static void +km_row_map_clear( + km_row_map_t * const row_map, const size_t num_rows ) { - // alloc row map - km_row_map_t * const row_map = malloc(sizeof(km_row_map_t) * num_rows); - - // check for error - if (!row_map) { - // return failure - return false; - } - // init row map + #pragma omp parallel for for (size_t i = 0; i < num_rows; i++) { // setting distances to maximum row_map[i].d2 = FLT_MAX; row_map[i].d2_near = FLT_MAX; } - - // return row map - return row_map; -} - -static void -km_row_map_fini( - km_row_map_t * const row_map -) { - free(row_map); } // use k-means to iteratively update the cluster centroids until there @@ -44,18 +26,15 @@ bool km_solve( km_set_t * const cs, const km_set_t * const set, + km_row_map_t * const row_map, const km_solve_cbs_t * const cbs, void * const cb_data ) { const size_t num_clusters = cs->num_rows, num_floats = set->shape.num_floats; - // row map: row => distance, cluster ID - km_row_map_t *row_map = km_row_map_init(set->num_rows); - if (!row_map) { - // return failure - return false; - } + // clear row map distances + km_row_map_clear(row_map, set->num_rows); // calculate clusters by doing the following: // * walk all clusters and all rows @@ -68,11 +47,13 @@ km_solve( // no changes yet changed = false; + #pragma omp parallel for collapse(2) for (size_t i = 0; i < num_clusters; i++) { - // get the floats for this cluster - const float * const floats = km_set_get_row(cs, i); - for (size_t j = 0; j < set->num_rows; j++) { + // get the floats for this cluster + // NOTE: moved to inner loop for "collapse(2)" above + const float * const floats = km_set_get_row(cs, i); + // get row values const float * const vals = km_set_get_row(set, j); @@ -101,7 +82,8 @@ km_solve( // if there were changes, then we need to calculate the new // cluster centers - // calculate new center + // calculate new cluster centers + #pragma omp parallel for for (size_t i = 0; i < num_clusters; i++) { size_t num_rows = 0; float * const floats = km_set_get_row(cs, i); @@ -141,30 +123,31 @@ km_solve( if (cbs && cbs->on_stats) { float sum = 0, - silouette = 0; + silhouette = 0; - // calculate mean numerators and silouette + // calculate mean numerators and silhouette + #pragma omp parallel for reduction(+:sum,silhouette) for (size_t i = 0; i < set->num_rows; i++) { - // sum distances - sum += row_map[i].d2; - - // calculate silouette denominator + // calculate silhouette denominator // (https://en.wikipedia.org/wiki/Silhouette_%28clustering%29) const float delta = (row_map[i].d2_near - row_map[i].d2); - // sum silouette - silouette += (delta < -MIN_DELTA || delta > MIN_DELTA) + // sum silhouette + silhouette += (delta < -MIN_DELTA || delta > MIN_DELTA) ? (delta / MAX(row_map[i].d2, row_map[i].d2_near)) : 0.0; + + // sum distances + sum += row_map[i].d2; } - // finalize silouette - silouette /= set->num_rows; + // finalize silhouette + silhouette /= set->num_rows; // build stats const km_solve_stats_t stats = { .sum = sum, - .silouette = silouette, + .silhouette = silhouette, .num_clusters = num_clusters, }; @@ -172,9 +155,6 @@ km_solve( cbs->on_stats(cs, &stats, cb_data); } - // free row_map - km_row_map_fini(row_map); - // return success return true; } @@ -94,7 +94,7 @@ typedef struct { typedef struct { const float sum; - const float silouette; + const float silhouette; const size_t num_clusters; } km_solve_stats_t; @@ -109,6 +109,7 @@ _Bool km_solve( km_set_t * const, const km_set_t * const, + km_row_map_t * const, const km_solve_cbs_t * const, void * const ); @@ -117,7 +118,7 @@ typedef struct { const km_set_t * const cluster_set; float distance_sum, - silouette, + silhouette, mean_cluster_size; const size_t num_clusters, @@ -41,7 +41,7 @@ typedef struct { struct { float distance, - silouette, + silhouette, cluster_size; size_t num_empty; } rows[MAX_CLUSTERS - 2]; @@ -163,7 +163,7 @@ find_on_data( const size_t ofs = data->num_clusters - 2; ctx->rows[ofs].distance += data->distance_sum; - ctx->rows[ofs].silouette += data->silouette; + ctx->rows[ofs].silhouette += data->silhouette; ctx->rows[ofs].cluster_size += data->mean_cluster_size; ctx->rows[ofs].num_empty += data->num_empty_clusters; } |