Skip to content

Instantly share code, notes, and snippets.

@qubyte
Created November 13, 2012 08:51
Show Gist options
  • Save qubyte/4064710 to your computer and use it in GitHub Desktop.
Save qubyte/4064710 to your computer and use it in GitHub Desktop.
Calculate a running standard deviation.
// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
function StandardDeviation(firstMeasurement) {
this.workData = firstMeasurement;
this.lastWorkData = null;
this.S = 0;
this.count = 1;
}
// Add a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
StandardDeviation.prototype.addMeasurement = function (measurement) {
this.count += 1;
this.lastWorkData = this.workData;
this.workData = this.workData + (measurement - this.workData) / this.count;
this.S = this.S + (measurement - this.lastWorkData) * (measurement - this.workData);
};
// Performs the final step needed to get the standard deviation and returns it.
StandardDeviation.prototype.get = function () {
return Math.sqrt(this.S / (this.count - 1));
};
@qubyte
Copy link
Author

qubyte commented Nov 13, 2012

The beauty behind this algorithm is that it doesn't need an entire dataset to be kept (it's single pass), and it's reasonably resistant to floating point errors.

@conradoqg
Copy link

Improved version that adds replace and removeMeasurement. Based on the anwsers provided by marco and Deleting Values in Welford’s Algorithm for Online Mean and Variance

// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
function StandardDeviation(firstMeasurement) {
    this.workData = firstMeasurement;
    this.lastWorkData = null;
    this.S = 0;
    this.count = 1;
}

// Add a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
StandardDeviation.prototype.addMeasurement = function (measurement) {
    this.count += 1;
    this.lastWorkData = this.workData;
    this.workData = this.workData + (measurement - this.workData) / this.count;
    this.S = this.S + (measurement - this.lastWorkData) * (measurement - this.workData);
};

// Performs the final step needed to get the standard deviation and returns it.
StandardDeviation.prototype.get = function () {
    return Math.sqrt(this.S / (this.count - 1));
};

// Replaces the value x currently present in this sample with the
// new value y. In a sliding window, x is the value that
// drops out and y is the new value entering the window. The sample
// count remains constant with this operation.
StandardDeviation.prototype.replace = function (x, y) {
    const deltaYX = y - x;
    const deltaX = x - this.workData;
    const deltaY = y - this.workData;
    this.workData = this.workData + deltaYX / this.count;
    const deltaYp = y - this.workData;
    const countMinus1 = this.count - 1;
    this.S = this.S - this.count / countMinus1 * (deltaX * deltaX - deltaY * deltaYp) - deltaYX * deltaYp / countMinus1;
};

// Remove a measurement. Also calculates updates to stepwise parameters which are later used
// to determine sigma.
StandardDeviation.prototype.removeMeasurement = function (x) {
    this.lastWorkData = (this.count * this.workData - x) / (this.count - 1);
    this.S -= (x - this.workData) * (x - this.lastWorkData);
    this.workData = this.lastWorkData;
    this.count -= 1;
};

@lu4
Copy link

lu4 commented Dec 1, 2020

Below is typescript version, it's more convenient to have a class with empty constructor since it imposes less constraints on when this class can be initialized (before you have your first value or after):

// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
export class StandardDeviation {
    public v: number = 0;
    private w: number = 0;
    private S: number = 0;
    private count: number = 0;

    // Add a measurement. Also calculates updates to stepwise parameters which are later used
    // to determine sigma.
    public add(measurement: number) {
        this.count += 1;
        this.w = this.v;
        this.v = this.v + (measurement - this.v) / this.count;
        this.S = this.S + (measurement - this.w) * (measurement - this.v);
    }

    // Performs the final step needed to get the standard deviation and returns it.
    public get() {
        if (this.count < 2) {
            // There are less measurements accumulated than necessary to perform computation
            return 0.0;
        } else {
            return Math.sqrt(this.S / (this.count - 1));
        }
    }

    // Replaces the value x currently present in this sample with the
    // new value y. In a sliding window, x is the value that
    // drops out and y is the new value entering the window. The sample
    // count remains constant with this operation.
    public replace(x: number, y: number) {
        const deltaYX = y - x;
        const deltaX = x - this.v;
        const deltaY = y - this.v;
        this.v = this.v + deltaYX / this.count;
        const deltaYp = y - this.v;
        const countMinus1 = this.count - 1;
        this.S = this.S - this.count / countMinus1 * (deltaX * deltaX - deltaY * deltaYp) - deltaYX * deltaYp / countMinus1;
    }

    // Remove a measurement. Also calculates updates to stepwise parameters which are later used
    // to determine sigma.
    public remove(x: number) {
        this.w = (this.count * this.v - x) / (this.count - 1);
        this.S -= (x - this.v) * (x - this.w);
        this.v = this.w;
        this.count -= 1;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment