3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 #include "Histogram.hh"
37 Histogram::Histogram(int binsize
, int bins
)
44 Histogram::~Histogram()
48 void Histogram::clear(int binsize
, int bins
)
54 void Histogram::clear(int bins
)
59 m_data
.setSize(m_bins
);
60 for (int i
= 0; i
< m_bins
; i
++) {
67 m_sumSquaredSamples
= 0;
71 void Histogram::add(int64 value
)
74 m_max
= max(m_max
, value
);
77 m_sumSamples
+= value
;
78 m_sumSquaredSamples
+= (value
*value
);
81 if (m_binsize
== -1) {
82 // This is a log base 2 histogram
86 index
= int(log(double(value
))/log(2.0))+1;
87 if (index
>= m_data
.size()) {
88 index
= m_data
.size()-1;
92 // This is a linear histogram
93 while (m_max
>= (m_bins
* m_binsize
)) {
94 for (int i
= 0; i
< m_bins
/2; i
++) {
95 m_data
[i
] = m_data
[i
*2] + m_data
[i
*2 + 1];
97 for (int i
= m_bins
/2; i
< m_bins
; i
++) {
102 index
= value
/m_binsize
;
106 m_largest_bin
= max(m_largest_bin
, index
);
109 void Histogram::add(const Histogram
& hist
)
111 assert(hist
.getBins() == m_bins
);
112 assert(hist
.getBinSize() == -1); // assume log histogram
113 assert(m_binsize
== -1);
115 for (int j
= 0; j
< hist
.getData(0); j
++) {
119 for (int i
= 1; i
< m_bins
; i
++) {
120 for (int j
= 0; j
< hist
.getData(i
); j
++) {
121 add(1<<(i
-1)); // account for the + 1 index
127 // Computation of standard deviation of samples a1, a2, ... aN
128 // variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
129 // std deviation equals square root of variance
130 double Histogram::getStandardDeviation() const
134 variance
= (double)(m_sumSquaredSamples
- m_sumSamples
*m_sumSamples
/m_count
)/(m_count
- 1);
138 return sqrt(variance
);
141 void Histogram::print(ostream
& out
) const
143 printWithMultiplier(out
, 1.0);
146 void Histogram::printPercent(ostream
& out
) const
149 printWithMultiplier(out
, 0.0);
151 printWithMultiplier(out
, 100.0/double(m_count
));
155 void Histogram::printWithMultiplier(ostream
& out
, double multiplier
) const
157 if (m_binsize
== -1) {
158 out
<< "[binsize: log2 ";
160 out
<< "[binsize: " << m_binsize
<< " ";
162 out
<< "max: " << m_max
<< " ";
163 out
<< "count: " << m_count
<< " ";
164 // out << "total: " << m_sumSamples << " ";
166 out
<< "average: NaN |";
167 out
<< "standard deviation: NaN |";
169 out
<< "average: " << setw(5) << ((double) m_sumSamples
)/m_count
<< " | ";
170 out
<< "standard deviation: " << getStandardDeviation() << " |";
172 for (int i
= 0; i
< m_bins
&& i
<= m_largest_bin
; i
++) {
173 if (multiplier
== 1.0) {
174 out
<< " " << m_data
[i
];
176 out
<< " " << double(m_data
[i
]) * multiplier
;
182 bool node_less_then_eq(const Histogram
* n1
, const Histogram
* n2
)
184 return (n1
->size() > n2
->size());