Created
August 7, 2022 19:00
-
-
Save faceslog/c3eb48bf0432a082a22e27ecbf381a0e to your computer and use it in GitHub Desktop.
Welford's online algorithm (C++) often useful to be able to compute the variance in a single pass
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma once | |
#include <cmath> | |
// Welford's online algorithm: | |
// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm | |
// It is often useful to be able to compute the variance in a single pass | |
/** | |
* EXAMPLE: | |
* | |
* std::vector<int> grades = { 12, 11, 14, 15, 16, 17, 8, 10 }; | |
* Welford accum{}; | |
* | |
* for (auto& grade : grades) | |
* accum.add_value(float(grade)); | |
* | |
* std::cout << "Size: " << accum.size() << std::endl; | |
* std::cout << "Mean: " << accum.mean() << std::endl; | |
* std::cout << "Var : " << accum.var() << std::endl; | |
* std::cout << "Sd : " << accum.sd() << std::endl; | |
*/ | |
class Welford { | |
public: | |
explicit Welford() | |
{ | |
n = 0; | |
m = ss = 0.0f; | |
} | |
~Welford() = default; | |
// Add a value to the accumulator | |
void add_value(float x) | |
{ | |
n++; | |
float delta = x - m; | |
m += delta / n; | |
float delta2 = x - m; | |
ss += delta * delta2; | |
} | |
// Get the mean | |
float mean() | |
{ | |
return m; | |
} | |
// Get the variance | |
float var() | |
{ | |
if (n <= 1) | |
return 0.0f; | |
return ss / (n - 1); | |
} | |
// Get the standard derivation | |
float sd() | |
{ | |
return sqrt(var()); | |
} | |
// Get the size of the population | |
int size() | |
{ | |
return n; | |
} | |
private: | |
// Mean | |
float m; | |
// Sum-of-squares | |
float ss; | |
// Size | |
int n; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment