Accumulator.java
4.53 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/******************************************************************************
* Compilation: javac Accumulator.java
* Execution: java Accumulator < input.txt
* Dependencies: StdOut.java StdIn.java
*
* Mutable data type that calculates the mean, sample standard
* deviation, and sample variance of a stream of real numbers
* use a stable, one-pass algorithm.
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code Accumulator} class is a data type for computing the running
* mean, sample standard deviation, and sample variance of a stream of real
* numbers. It provides an example of a mutable data type and a streaming
* algorithm.
* <p>
* This implementation uses a one-pass algorithm that is less susceptible
* to floating-point roundoff error than the more straightforward
* implementation based on saving the sum of the squares of the numbers.
* This technique is due to
* <a href = "https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm">B. P. Welford</a>.
* Each operation takes constant time in the worst case.
* The amount of memory is constant - the data values are not stored.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/12oop">Section 1.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Accumulator {
private int n = 0; // number of data values
private double sum = 0.0; // sample variance * (n-1)
private double mu = 0.0; // sample mean
/**
* Initializes an accumulator.
*/
public Accumulator() {
}
/**
* Adds the specified data value to the accumulator.
* @param x the data value
*/
public void addDataValue(double x) {
n++;
double delta = x - mu;
mu += delta / n;
sum += (double) (n - 1) / n * delta * delta;
}
/**
* Returns the mean of the data values.
* @return the mean of the data values
*/
public double mean() {
return mu;
}
/**
* Returns the sample variance of the data values.
* @return the sample variance of the data values
*/
public double var() {
return sum / (n - 1);
}
/**
* Returns the sample standard deviation of the data values.
* @return the sample standard deviation of the data values
*/
public double stddev() {
return Math.sqrt(this.var());
}
/**
* Returns the number of data values.
* @return the number of data values
*/
public int count() {
return n;
}
/**
* Unit tests the {@code Accumulator} data type.
* Reads in a stream of real number from standard input;
* adds them to the accumulator; and prints the mean,
* sample standard deviation, and sample variance to standard
* output.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Accumulator stats = new Accumulator();
while (!StdIn.isEmpty()) {
double x = StdIn.readDouble();
stats.addDataValue(x);
}
StdOut.printf("n = %d\n", stats.count());
StdOut.printf("mean = %.5f\n", stats.mean());
StdOut.printf("stddev = %.5f\n", stats.stddev());
StdOut.printf("var = %.5f\n", stats.var());
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/