From 05c10f940f9df3a5b24e2a0b476052fbe5a22282 Mon Sep 17 00:00:00 2001 From: Damien Lespiau Date: Thu, 25 Jun 2015 23:57:49 +0100 Subject: stats: Use an algorithm popularised by Knuth to compute mean and variance Suggested-by: Chris Wilson Signed-off-by: Damien Lespiau --- lib/igt_stats.c | 42 +++++++++++++++++++++++++++++++++++++----- 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); -- cgit v1.2.3