diff options
author | Damien Lespiau <damien.lespiau@intel.com> | 2015-06-25 23:57:49 +0100 |
---|---|---|
committer | Damien Lespiau <damien.lespiau@intel.com> | 2015-06-27 16:03:27 +0100 |
commit | 05c10f940f9df3a5b24e2a0b476052fbe5a22282 (patch) | |
tree | b1f99b0cd722b7d6da6c9695d090932c7c3050ad | |
parent | 9986282c2bb4508a1fd9b774e30e1f4e405ac82e (diff) |
stats: Use an algorithm popularised by Knuth to compute mean and variance
Suggested-by: Chris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
-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); |