Swift Array extension for standard deviation

Question

I am frequently needing to calculate mean and standard deviation for numeric arrays. So I've written a small protocol and extensions for numeric types that seems to work. I just would like feedback if there is anything wrong with how I have done this. Specifically, I am wondering if there is a better way to check if the type can be cast as a Double to avoid the need for the asDouble variable and init(_:Double) constructor.

I know there are issues with protocols that allow for arithmetic, but this seems to work ok and saves me from putting the standard deviation function into classes that need it.

protocol Numeric {
    var asDouble: Double { get }
    init(_: Double)
}

extension Int: Numeric {var asDouble: Double { get {return Double(self)}}}
extension Float: Numeric {var asDouble: Double { get {return Double(self)}}}
extension Double: Numeric {var asDouble: Double { get {return Double(self)}}}
extension CGFloat: Numeric {var asDouble: Double { get {return Double(self)}}}

extension Array where Element: Numeric {

    var mean : Element { get { return Element(self.reduce(0, combine: {$0.asDouble + $1.asDouble}) / Double(self.count))}}

    var sd : Element { get {
        let mu = self.reduce(0, combine: {$0.asDouble + $1.asDouble}) / Double(self.count)
        let variances = self.map{pow(($0.asDouble - mu), 2)}
        return Element(sqrt(variances.mean))
    }}
}

edit: I know it's kind of pointless to get [Int].mean and sd, but I might use numeric elsewhere so it's for consistency..

edit: as @Severin Pappadeux pointed out, variance can be expressed in a manner that avoids the triple pass on the array - mean then map then mean. Here is the final standard deviation extension

extension Array where Element: Numeric {

    var sd : Element { get {
        let sss = self.reduce((0.0, 0.0)){ return ($0.0 + $1.asDouble, $0.1 + ($1.asDouble * $1.asDouble))}
        let n = Double(self.count)
        return Element(sqrt(sss.1/n - (sss.0/n * sss.0/n)))
    }}
}

Brillatsavarin

Int is generally the same size as Int64 on newer devices (>= iPhone 5S, which introduced the 64bit processor), so unless you're working with really large numbers, this shouldn't be an issue: but just know that init(_: Double) can lead to an integer overflow (runtime exception) in cases where the Element = Int type cannot store the integer representation of a given (huge) Double value. Possibly not an issue if you just use your Swift apps yourself, but in case you ship to customers, this might be good to bear in mind. – Wrongdoing

Ok interesting thanks. It's unlikely I will use it with integers, and the values I'm working with are physiologically constrained to < 500 with this app. So should be ok. – Brillatsavarin

@dfri very useful comment! I presume that there is no way to "catch" this kind of overflow? – Runofthemine

@Runofthemine Thanks! I guess we could include a static min and max property in Numeric and check the double representation (under the assumption that all numeric values can can be seen as "kind of" as subset of the range of valid Double values; i.e., always convertible to Double without any risk of overflow on that part, but I guess in worst case we get Double.infinity) of this property vs the Double valued sum from the reduce operation above. E.g. something along these lines. – Wrongdoing

@dfri I may be wrong, but from reading over the new FloatingPoint protocol in Swift 3, I think it might save you some work in that gist. — It's funny, though, how you can "catch" overflow when adding two Ints (by using a special operator) but you can't "catch" it when coercing to a Double. – Runofthemine

@Runofthemine Ah, I didn't look at any Swift 3 goodies for this fix, but it would be nice if the type extensions could be less messy (cleaned up the Array extension in the gist somewhat with a help function). Yeah I agree, my first thought was going straight for the &+ operators, but I guess we don't (yet) have any similar for type conversions (failable initializers for such type coercion could be a nice addition). – Wrongdoing

Where can I read about this FloatingPoint protocol, or view it? Google is failing me or I am failing at google. – Brillatsavarin

@Brillatsavarin Its not yet in the "official" docs, but can be found at Swift evolution: proposal SE-0067: Enhanced Floating Point Protocols. – Wrongdoing

@Brillatsavarin swiftdoc.org/v3.0/protocol/FloatingPoint – Runofthemine

Answer 1

In Swift 3 you might (or might not) be able to save yourself some duplication with the FloatingPoint protocol, but otherwise what you're doing is exactly right.

Runofthemine

Answer 2

Swift 4 Array extension with FloatingPoint elements:

extension Array where Element: FloatingPoint {

    func sum() -> Element {
        return self.reduce(0, +)
    }

    func avg() -> Element {
        return self.sum() / Element(self.count)
    }

    func std() -> Element {
        let mean = self.avg()
        let v = self.reduce(0, { $0 + ($1-mean)*($1-mean) })
        return sqrt(v / (Element(self.count) - 1))
    }

}

Colourable

Note that this is making use of Bessel's Correction: en.wikipedia.org/wiki/Bessel%27s_correction. See also #27600707 – Encore

Answer 3

There's actually a class that provides this functionality already - called NSExpression. You could reduce your code size and complexity by using this instead. There's quite a bit of stuff to this class, but a simple implementation of what you want is as follows.

let expression = NSExpression(forFunction: "stddev:", arguments: [NSExpression(forConstantValue: [1,2,3,4,5])])
let standardDeviation = expression.expressionValueWithObject(nil, context: nil)

You can calculate mean too, and much more. Info here: http://nshipster.com/nsexpression/

Misunderstood

Be careful if you intend to port to Linux - NSExpression is not implemented there. – Furey

Answer 4

To follow up on Matt's observation, I'd do the main algorithm on FloatingPoint, taking care of Double, Float, CGFloat, etc. But then I then do another permutation of this on BinaryInteger, to take care of all of the integer types.

E.g. on FloatingPoint:

extension Array where Element: FloatingPoint {
    
    /// The mean average of the items in the collection.
    
    var mean: Element { return reduce(Element(0), +) / Element(count) }
    
    /// The unbiased sample standard deviation. Is `nil` if there are insufficient number of items in the collection.
    
    var stdev: Element? {
        guard count > 1 else { return nil }
        
        return sqrt(sumSquaredDeviations() / Element(count - 1))
    }
    
    /// The population standard deviation. Is `nil` if there are insufficient number of items in the collection.
    
    var stdevp: Element? {
        guard count > 0 else { return nil }
        
        return sqrt(sumSquaredDeviations() / Element(count))
    }
    
    /// Calculate the sum of the squares of the differences of the values from the mean
    ///
    /// A calculation common for both sample and population standard deviations.
    ///
    /// - calculate mean
    /// - calculate deviation of each value from that mean
    /// - square that
    /// - sum all of those squares
    
    private func sumSquaredDeviations() -> Element {
        let average = mean
        return map {
            let difference = $0 - average
            return difference * difference
        }.reduce(Element(0), +)
    }
}

But then on BinaryInteger:

extension Array where Element: BinaryInteger {
    var mean: Double { return map { Double(exactly: $0)! }.mean }
    var stdev: Double? { return map { Double(exactly: $0)! }.stdev }
    var stdevp: Double? { return map { Double(exactly: $0)! }.stdevp }
}

Note, in my scenario, even when dealing with integer input data, I generally want floating point mean and standard deviations, so I arbitrarily chose Double. And you might want to do safer unwrapping of Double(exactly:). You can handle this scenario any way you want. But it illustrates the idea.

Caniff

Answer 5

Not that I know Swift, but from numerics POV you're doing it a bit inefficiently

Basically, you're doing two passes (actually, three) over the array to compute two values, where one pass should be enough. Vairance might be expressed as E(X²) - E(X)², so in some pseudo-code:

tuple<float,float> get_mean_sd(data) {
    float s  = 0.0f;
    float s2 = 0.0f;
    for(float v: data) {
        s  += v;
        s2 += v*v;
    }
    s  /= count;
    s2 /= count;

    s2 -= s*s;
    return tuple(s, sqrt(s2 > 0.0 ? s2 : 0.0));
}

Minsk

You're right. Thank you, this does avoid the triple pass. – Brillatsavarin

@Brillatsavarin you're welcome, though I'm curious if it could be expressed via reduce() – Minsk

Got it: let s = self.reduce((0.0, 0.0)){ return ($0.0 + $1.asDouble, $0.1 + ($1.asDouble * $1.asDouble))} then s.1/n - s.0/n * s.0/n. Sorry for the horrible formatting. New to this. – Brillatsavarin

Answer 6

Just a heads-up, but when I tested the code outlined by Severin Pappadeux the result was a "population standard deviation" rather than a "sample standard deviation". You would use the first in an instance where 100% of the relevant data is available to you, such as when you are computing the variance around an average grade for all 20 students in a class. You would use the second if you did not have universal access to all the relevant data, and had to estimate the variance from a much smaller sample, such as estimating the height of all males within a large country.

The population standard deviation is often denoted as StDevP. The Swift 5.0 code I used is shown below. Note that this is not suitable for very large arrays due to loss of the "small value" bits as the summations get large. Especially when the variance is close to zero you might run into run-times errors. For such serious work you might have to introduce an algorithm called compensated summation

import Foundation

extension Array where Element: FloatingPoint
{

    var sum: Element {
        return self.reduce( 0, + )
    }
    
    var average: Element {
        return self.sum / Element( count )
    }
    
    /**
     (for a floating point array) returns a tuple containing the average and the "standard deviation for populations"
     */
    var averageAndStandardDeviationP: ( average: Element, stDevP: Element ) {
        
        let sumsTuple = sumAndSumSquared
        
        let populationSize = Element( count )
        let average = sumsTuple.sum / populationSize
        
        let expectedXSquared = sumsTuple.sumSquared / populationSize
        let variance = expectedXSquared - (average * average )
        
        return ( average, sqrt( variance ) )
    }
    
    /**
     (for a floating point array) returns a tuple containing the sum of all the values and the sum of all the values-squared
     */
    private var sumAndSumSquared: ( sum: Element, sumSquared: Element ) {
        return self.reduce( (Element(0), Element(0) ) )
        {
            ( arg0, x) in
            let (sumOfX, sumOfSquaredX) = arg0
            return ( sumOfX + x, sumOfSquaredX + ( x * x ) )
        }
    }
}

Raber