diff options
-rw-r--r-- | lib/igt_stats.c | 42 | ||||
-rw-r--r-- | lib/igt_stats.h | 3 |
2 files changed, 40 insertions, 5 deletions
diff --git a/lib/igt_stats.c b/lib/igt_stats.c index e6babde6..20db806d 100644 --- a/lib/igt_stats.c +++ b/lib/igt_stats.c @@ -42,15 +42,47 @@ void igt_stats_push(igt_stats_t *stats, uint64_t value) { igt_assert(stats->n_values < stats->capacity); stats->values[stats->n_values++] = value; + stats->mean_variance_valid = false; } -double igt_stats_get_mean(igt_stats_t *stats) +/* + * Algorithm popularised by Knuth in: + * + * The Art of Computer Programming, volume 2: Seminumerical Algorithms, + * 3rd edn., p. 232. Boston: Addison-Wesley + * + * Source: https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance + */ +static void igt_stats_knuth_mean_variance(igt_stats_t *stats) { + double mean = 0., m2 = 0.; unsigned int i; - double a = 0.0; - for (i = 0; i < stats->n_values; i++) - a += (double)stats->values[i] / stats->n_values; + if (stats->mean_variance_valid) + return; + + for (i = 0; i < stats->n_values; i++) { + double delta = stats->values[i] - mean; + + mean += delta / (i + 1); + m2 += delta * (stats->values[i] - mean); + } + + stats->mean = mean; + stats->variance = m2 / stats->n_values; + stats->mean_variance_valid = true; +} + +double igt_stats_get_mean(igt_stats_t *stats) +{ + igt_stats_knuth_mean_variance(stats); + + return stats->mean; +} + +double igt_stats_get_variance(igt_stats_t *stats) +{ + igt_stats_knuth_mean_variance(stats); - return a; + return stats->variance; } diff --git a/lib/igt_stats.h b/lib/igt_stats.h index a46b399c..acb86a6b 100644 --- a/lib/igt_stats.h +++ b/lib/igt_stats.h @@ -28,9 +28,12 @@ typedef struct { uint64_t *values; unsigned int capacity; unsigned int n_values; + unsigned int mean_variance_valid : 1; + double mean, variance; } igt_stats_t; void igt_stats_init(igt_stats_t *stats, unsigned int capacity); void igt_stats_fini(igt_stats_t *stats); void igt_stats_push(igt_stats_t *stats, uint64_t value); double igt_stats_get_mean(igt_stats_t *stats); +double igt_stats_get_variance(igt_stats_t *stats); |