1 /*******************************************************************************
2 * Copyright (c) 2015, 2016 Ericsson
4 * All rights reserved. This program and the accompanying materials are made
5 * available under the terms of the Eclipse Public License v1.0 which
6 * accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * Bernd Hufmann - Initial API and implementation
11 *******************************************************************************/
12 package org
.eclipse
.tracecompass
.analysis
.timing
.core
.segmentstore
.statistics
;
14 import org
.eclipse
.tracecompass
.segmentstore
.core
.BasicSegment
;
15 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
18 * Class to calculate simple segment store statistics (min, max, average)
20 * @author Bernd Hufmann
22 public class SegmentStoreStatistics
{
23 private ISegment fMin
;
24 private ISegment fMax
;
25 private long fNbSegments
;
26 private double fAverage
;
28 * reminder, this is the variance * nb elem, as per the online algorithm
30 private double fVariance
;
31 private double fTotal
;
36 public SegmentStoreStatistics() {
37 fMin
= new BasicSegment(0, Long
.MAX_VALUE
);
38 fMax
= new BasicSegment(Long
.MIN_VALUE
, 0);
48 * @return minimum value
50 public long getMin() {
51 return fMin
.getLength();
57 * @return maximum value
59 public long getMax() {
60 return fMax
.getLength();
64 * Get segment with minimum length
66 * @return segment with minimum length
68 public ISegment
getMinSegment() {
73 * Get segment with maximum length
75 * @return segment with maximum length
77 public ISegment
getMaxSegment() {
82 * Get number of segments analyzed
84 * @return number of segments analyzed
86 public long getNbSegments() {
91 * Gets the arithmetic average
93 * @return arithmetic average
95 public double getAverage() {
100 * Gets the standard deviation of the segments, uses the online algorithm
101 * shown here <a href=
102 * "https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm">
103 * Wikipedia article of dec 3 2015 </a>
105 * @return the standard deviation of the segment store, will return NaN if
106 * there are less than 3 elements
108 public double getStdDev() {
109 return fNbSegments
> 2 ? Math
.sqrt(fVariance
/ (fNbSegments
- 1)) : Double
.NaN
;
115 * @return total value
118 public double getTotal() {
123 * Update the statistics based on a given segment
125 * This is an online algorithm and must retain a complexity of O(1)
128 * the segment used for the update
130 public void update(ISegment segment
) {
131 long value
= segment
.getLength();
133 * Min and max are trivial, as well as number of segments
135 long min
= fMin
.getLength();
136 long max
= fMax
.getLength();
137 fMin
= min
<= value ? fMin
: segment
;
138 fMax
= max
>= value ? fMax
: segment
;
142 * The running mean is not trivial, see proof in javadoc.
144 double delta
= value
- fAverage
;
145 fAverage
+= delta
/ fNbSegments
;
146 fVariance
+= delta
* (value
- fAverage
);
151 * Merge two statistics sets. If the pools are large, there may be a slight
152 * approximation error (empirically, the error is at most 0.001 but usually
153 * around 1e-5 for the standard deviation as this uses pooled variance.
156 * The other segment store statistics
159 public void merge(SegmentStoreStatistics other
) {
160 if (other
.fNbSegments
== 0) {
162 } else if (fNbSegments
== 0) {
164 } else if (other
.fNbSegments
== 1) {
166 } else if (fNbSegments
== 1) {
167 SegmentStoreStatistics copyOther
= new SegmentStoreStatistics();
168 copyOther
.copy(other
);
169 copyOther
.update(fMax
);
172 internalMerge(other
);
176 private void internalMerge(SegmentStoreStatistics other
) {
178 * Min and max are trivial, as well as number of segments
180 long min
= fMin
.getLength();
181 long max
= fMax
.getLength();
182 fMin
= min
<= other
.getMin() ? fMin
: other
.getMinSegment();
183 fMax
= max
>= other
.getMax() ? fMax
: other
.getMaxSegment();
185 long oldNbSeg
= fNbSegments
;
186 double oldAverage
= fAverage
;
187 long otherSegments
= other
.getNbSegments();
188 double otherAverage
= other
.getAverage();
189 fNbSegments
+= otherSegments
;
190 fTotal
+= other
.getTotal();
193 * Average is a weighted average
195 fAverage
= ((oldNbSeg
* oldAverage
) + (otherAverage
* otherSegments
)) / fNbSegments
;
198 * This one is a bit tricky.
200 * The variance is the sum of the deltas from a mean squared.
202 * So if we add the old mean squared back to to variance and remove the
203 * new mean, the standard deviation can be easily calculated.
205 double avg1Sq
= oldAverage
* oldAverage
;
206 double avg2sq
= otherAverage
* otherAverage
;
207 double avgtSq
= fAverage
* fAverage
;
209 * This is a tricky part, bear in mind that the set is not continuous but discrete,
210 * Therefore, we have for n elements, n-1 intervals between them.
211 * Ergo, n-1 intervals are used for divisions and multiplications.
213 double variance1
= fVariance
/ (oldNbSeg
- 1);
214 double variance2
= other
.fVariance
/ (otherSegments
- 1);
215 fVariance
= ((variance1
+ avg1Sq
- avgtSq
) * (oldNbSeg
- 1) + (variance2
+ avg2sq
- avgtSq
) * (otherSegments
- 1));
218 private void copy(SegmentStoreStatistics copyOther
) {
219 fAverage
= copyOther
.fAverage
;
220 fMax
= copyOther
.fMax
;
221 fMin
= copyOther
.fMin
;
222 fNbSegments
= copyOther
.fNbSegments
;
223 fTotal
= copyOther
.fTotal
;
224 fVariance
= copyOther
.fVariance
;