Skip to content

Instantly share code, notes, and snippets.

@faceslog
Created August 7, 2022 19:00
Show Gist options
  • Save faceslog/c3eb48bf0432a082a22e27ecbf381a0e to your computer and use it in GitHub Desktop.
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
#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