001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.statistics.descriptive; 018 019/** 020 * Computes the standard deviation of the available values. The default implementation uses the 021 * following definition of the <em>sample standard deviation</em>: 022 * 023 * <p>\[ \sqrt{ \tfrac{1}{n-1} \sum_{i=1}^n (x_i-\overline{x})^2 } \] 024 * 025 * <p>where \( \overline{x} \) is the sample mean, and \( n \) is the number of samples. 026 * 027 * <ul> 028 * <li>The result is {@code NaN} if no values are added. 029 * <li>The result is zero if there is one value in the data set. 030 * </ul> 031 * 032 * <p>The use of the term \( n − 1 \) is called Bessel's correction. Omitting the square root, 033 * this provides an unbiased estimator of the variance of a hypothetical infinite population. If the 034 * {@link #setBiased(boolean) biased} option is enabled the normalisation factor is 035 * changed to \( \frac{1}{n} \) for a biased estimator of the <em>sample variance</em>. 036 * Note however that square root is a concave function and thus introduces negative bias 037 * (by Jensen's inequality), which depends on the distribution, and thus the corrected sample 038 * standard deviation (using Bessel's correction) is less biased, but still biased. 039 * 040 * <p>The implementation uses an exact integer sum to compute the scaled (by \( n \)) 041 * sum of squared deviations from the mean; this is normalised by the scaled correction factor. 042 * 043 * <p>\[ \frac {n \times \sum_{i=1}^n x_i^2 - (\sum_{i=1}^n x_i)^2}{n \times (n - 1)} \] 044 * 045 * <p>Supports up to 2<sup>63</sup> (exclusive) observations. 046 * This implementation does not check for overflow of the count. 047 * 048 * <p>This class is designed to work with (though does not require) 049 * {@linkplain java.util.stream streams}. 050 * 051 * <p><strong>This implementation is not thread safe.</strong> 052 * If multiple threads access an instance of this class concurrently, 053 * and at least one of the threads invokes the {@link java.util.function.IntConsumer#accept(int) accept} or 054 * {@link StatisticAccumulator#combine(StatisticResult) combine} method, it must be synchronized externally. 055 * 056 * <p>However, it is safe to use {@link java.util.function.IntConsumer#accept(int) accept} 057 * and {@link StatisticAccumulator#combine(StatisticResult) combine} 058 * as {@code accumulator} and {@code combiner} functions of 059 * {@link java.util.stream.Collector Collector} on a parallel stream, 060 * because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()} 061 * provides the necessary partitioning, isolation, and merging of results for 062 * safe and efficient parallel execution. 063 * 064 * @see <a href="https://en.wikipedia.org/wiki/Standard_deviation">Standard deviation (Wikipedia)</a> 065 * @see <a href="https://en.wikipedia.org/wiki/Bessel%27s_correction">Bessel's correction</a> 066 * @see <a href="https://en.wikipedia.org/wiki/Jensen%27s_inequality">Jensen's inequality</a> 067 * @see IntVariance 068 * @since 1.1 069 */ 070public final class IntStandardDeviation implements IntStatistic, StatisticAccumulator<IntStandardDeviation> { 071 072 /** Sum of the squared values. */ 073 private final UInt128 sumSq; 074 /** Sum of the values. */ 075 private final Int128 sum; 076 /** Count of values that have been added. */ 077 private long n; 078 079 /** Flag to control if the statistic is biased, or should use a bias correction. */ 080 private boolean biased; 081 082 /** 083 * Create an instance. 084 */ 085 private IntStandardDeviation() { 086 this(UInt128.create(), Int128.create(), 0); 087 } 088 089 /** 090 * Create an instance. 091 * 092 * @param sumSq Sum of the squared values. 093 * @param sum Sum of the values. 094 * @param n Count of values that have been added. 095 */ 096 private IntStandardDeviation(UInt128 sumSq, Int128 sum, int n) { 097 this.sumSq = sumSq; 098 this.sum = sum; 099 this.n = n; 100 } 101 102 /** 103 * Creates an instance. 104 * 105 * <p>The initial result is {@code NaN}. 106 * 107 * @return {@code IntStandardDeviation} instance. 108 */ 109 public static IntStandardDeviation create() { 110 return new IntStandardDeviation(); 111 } 112 113 /** 114 * Returns an instance populated using the input {@code values}. 115 * 116 * @param values Values. 117 * @return {@code IntStandardDeviation} instance. 118 */ 119 public static IntStandardDeviation of(int... values) { 120 // Small arrays can be processed using the object 121 if (values.length < IntVariance.SMALL_SAMPLE) { 122 final IntStandardDeviation stat = new IntStandardDeviation(); 123 for (final int x : values) { 124 stat.accept(x); 125 } 126 return stat; 127 } 128 129 // Arrays can be processed using specialised counts knowing the maximum limit 130 // for an array is 2^31 values. 131 long s = 0; 132 final UInt96 ss = UInt96.create(); 133 // Process pairs as we know two maximum value int^2 will not overflow 134 // an unsigned long. 135 final int end = values.length & ~0x1; 136 for (int i = 0; i < end; i += 2) { 137 final long x = values[i]; 138 final long y = values[i + 1]; 139 s += x + y; 140 ss.addPositive(x * x + y * y); 141 } 142 if (end < values.length) { 143 final long x = values[end]; 144 s += x; 145 ss.addPositive(x * x); 146 } 147 148 // Convert 149 return new IntStandardDeviation(UInt128.of(ss), Int128.of(s), values.length); 150 } 151 152 /** 153 * Updates the state of the statistic to reflect the addition of {@code value}. 154 * 155 * @param value Value. 156 */ 157 @Override 158 public void accept(int value) { 159 sumSq.addPositive((long) value * value); 160 sum.add(value); 161 n++; 162 } 163 164 /** 165 * Gets the standard deviation of all input values. 166 * 167 * <p>When no values have been added, the result is {@code NaN}. 168 * 169 * @return standard deviation of all values. 170 */ 171 @Override 172 public double getAsDouble() { 173 return IntVariance.computeVarianceOrStd(sumSq, sum, n, biased, true); 174 } 175 176 @Override 177 public IntStandardDeviation combine(IntStandardDeviation other) { 178 sumSq.add(other.sumSq); 179 sum.add(other.sum); 180 n += other.n; 181 return this; 182 } 183 184 /** 185 * Sets the value of the biased flag. The default value is {@code false}. The bias 186 * term refers to the computation of the variance; the standard deviation is returned 187 * as the square root of the biased or unbiased <em>sample variance</em>. For further 188 * details see {@link IntVariance#setBiased(boolean) IntVarianceVariance.setBiased}. 189 * 190 * <p>This flag only controls the final computation of the statistic. The value of 191 * this flag will not affect compatibility between instances during a 192 * {@link #combine(IntStandardDeviation) combine} operation. 193 * 194 * @param v Value. 195 * @return {@code this} instance 196 * @see IntVariance#setBiased(boolean) 197 */ 198 public IntStandardDeviation setBiased(boolean v) { 199 biased = v; 200 return this; 201 } 202}