 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Irek Szczesniak
Guest
|
 Posted: Wed Oct 26, 2005 11:12 pm Post subject: a class for computing averages |
 |
|
I am looking for a class that would compute average values. I would
like to write something like this:
| Quote: | // we start at time 0, unit = 1, interval = 1, window = 10
avg<int, double> log(0, 1, 1, 10);
log.report(0, 5); // time = 0, value = 5.
log.report(0, 5);
log.report(0, 5);
log.report(1, 5);
log.report(1, 5);
log.report(10, 0);
|
And so I would expect the average of 2.5 for the interval [0-10).
I looked at Boost and didn't find it there. Finally I wrote my own
class, which does the job, but I would prefer some generic library.
Below I'm sending you the class and the test program.
Thanks for reading.
Best,
Irek
********************************************************
avg.h:
// -*- C++ -*-
#ifndef AVG_H
#define AVG_H
#include <iostream>
#include <map>
#include <vector>
#include <utility>
// Copyright Ireneusz Szczesniak, 2005
// License: GPL
// This class accumulates measurement values (samples), computes
// averages and returns a vector to these averages. Here we measure
// one value only. We average the measured value over a window of
// given size, and generate the averages periodically.
template<class T, class V>
class avg
{
public:
avg() : kickoff(0), unit(1), interval(1), wnd(1)
{
setup();
}
avg(T _kickoff, T _unit, T _interval, T _wnd) :
kickoff(_kickoff), unit(_unit), interval(_interval), wnd(_wnd)
{
setup();
}
void setup(void)
{
// This is the first time at which to generate an average.
trigger_time = kickoff + wnd;
}
// Use this function to report the samples. The argument "now" is
// the time, and the argument "value" is the measured value.
void report(T now, V value)
{
// Just ignore the values reported before the kickoff time.
if (now < kickoff)
return;
// Make sure we are not too last with this sample.
assert(now >= trigger_time - wnd);
// Here we are remembering the value for the later use.
recent_samples.insert(std::make_pair(now, value));
// Quit unless it's time to generate one or more averages.
if (now < trigger_time)
return;
typename std::multimap
// One iteration per interval
do
{
// Remove the items which are too old to be taken into account.
i = recent_samples.lower_bound(trigger_time - wnd);
recent_samples.erase(recent_samples.begin(), i);
// Here we are ready to calculate the average for a period.
// The average will be calculated from the items in
// recent_samples, which satisfy i->first < trigger_time.
// Note that the sample which arrived at the trigger time will
// be used to calculate next average, not this average. The
// range is [last_sample.begin(), i). The index i marks the
// border, but is not a part of the interval.
i = recent_samples.lower_bound(trigger_time);
// If i hits the end of the list, then must be a bug.
assert(i != recent_samples.end());
// Here we can finally produce the average.
V sum = 0;
while(i-- != recent_samples.begin())
sum += i->second;
averages.push_back(std::make_pair(trigger_time, sum * unit / wnd));
trigger_time += interval;
} while(trigger_time <= now);
}
// Use this function to get the vector of average values.
const std::vector &get_vector()
{
return averages;
}
private:
// The time at which we are supposed to start logging.
T kickoff;
// The time unit size.
T unit;
// The interval at which to generate average values.
T interval;
// The size of the window.
T wnd;
// This is the nearest time for generating an average.
T trigger_time;
// This multimap stores the values required to compute an average
// for an interval. Whenever a new sample is available, it's put in
// the multimap. The samples that have been processed are removed.
// We need a multimap, because some samples might be recorded at
// several equal times.
std::multimap<T, V> recent_samples;
// This map stores the computed averages.
std::vector<std::pair averages;
};
#endif
********************************************************************
avg_test.cc
#include <iostream>
#include "avg.h"
int main()
{
// start at 0, unit = 1, interval = 1, window = 10
avg<int, double> log(0, 1, 1, 10);
log.report(0, 5);
log.report(0, 5);
log.report(0, 5);
log.report(1, 5);
log.report(1, 5);
log.report(10, 0);
std::vector<std::pair v;
v = log.get_vector();
std::vector<std::pair::iterator i;
for(i = v.begin(); i != v.end(); i++)
std::cout << i->first << ", " << i->second << std::endl;
return 0;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Tony Delroy
Guest
|
| Posted: Thu Nov 03, 2005 10:54 am Post subject: Re: a class for computing averages |
|
|
Hi Irek,
Your post's gone a long time without comment, so I'll offer some of
dubious value. IMHO, your requirements are specific enough that they
won't have been implemented elsewhere, and further, the implementation
is so simple ('twould be more obviously so without the excessive and
redundant commenting) that's there's little incentive for such an
implementation to be developed or shared.
Further, most people probably wouldn't bother abstracting this
behaviour in a separate class, as it can be achieved directly over a
standard container by starting iteration at the lower_bound and adding
values while in the range, then dividing by the range.
Cheers,
Tony
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
NJS
Guest
|
| Posted: Fri Nov 04, 2005 10:56 am Post subject: Re: a class for computing averages |
|
|
You might want to check out the "Provisional Means Algorithm" for
computing your average. It breaks down the calculations into
difference equations. Maintaining a running mean and variance, it
allows for the removal and addition of data points on the fly.
Though not relevant to your problem, it also computes variance in a
single pass (naive method uses one pass to compute mean and a second
for variance). This is handy if you're working with large datasets
held on secondary storage (e.g. massive images on a harddisk).
A good explanation and derivation of the algorithm is here:
http://www.cmh.edu/stats/weblog2004/ProvisionalMeans.asp
A quickly hacked sample implementation can be found here:
http://www.cis.rit.edu/~njs8030/coding/variance.C
- Niek Sanders
www.cis.rit.edu/~njs8030/
Irek Szczesniak wrote:
| Quote: | I am looking for a class that would compute average values. I would
like to write something like this:
[snip]
|
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Irek Szczesniak
Guest
|
| Posted: Tue Nov 08, 2005 10:50 am Post subject: Re: a class for computing averages |
|
|
Hi Tony,
| Quote: | Your post's gone a long time without comment, so I'll offer some of
dubious value.
|
Thank you for your email. I'm glad someone responded.
| Quote: | IMHO, your requirements are specific enough that they won't have
been implemented elsewhere, and further, the implementation is so
simple ('twould be more obviously so without the excessive and
redundant commenting) that's there's little incentive for such an
implementation to be developed or shared.
Further, most people probably wouldn't bother abstracting this
behaviour in a separate class, as it can be achieved directly over a
standard container by starting iteration at the lower_bound and
adding values while in the range, then dividing by the range.
|
You are right to some extent. However, I guess that the
implementation isn't straight forward. Having a ready solution would
have saved me some time implementing my own class. Then you want the
library to be efficient, and possibly with little bugs. When you look
at my class, it's quite complicated, and I tried to make it nice and
simple. I don't think my class is great, and so I was hoping to find
something better already available.
Best,
Irek
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Alberto Ganesh Barbati
Guest
|
| Posted: Wed Nov 09, 2005 1:53 am Post subject: Re: a class for computing averages |
|
|
Irek Szczesniak wrote:
| Quote: | IMHO, your requirements are specific enough that they won't have
been implemented elsewhere, and further, the implementation is so
simple ('twould be more obviously so without the excessive and
redundant commenting) that's there's little incentive for such an
implementation to be developed or shared.
Further, most people probably wouldn't bother abstracting this
behaviour in a separate class, as it can be achieved directly over a
standard container by starting iteration at the lower_bound and
adding values while in the range, then dividing by the range.
You are right to some extent. However, I guess that the
implementation isn't straight forward. Having a ready solution would
have saved me some time implementing my own class. Then you want the
library to be efficient, and possibly with little bugs. When you look
at my class, it's quite complicated, and I tried to make it nice and
simple. I don't think my class is great, and so I was hoping to find
something better already available.
|
Of course, having ready-made, tested and robust code is always better
than wasting time writing it on your own, but you should consider that
your problem is not as common as you may think. I did not look at the
detail of your code, but it seems to me that you are doing more than
simple "averages" in there. For example, the presence of parameters
kickoff and interval, for example, is a clear hint that some logic
unrelated to "computing an average" is being done by the class.
However, what Tony was probably trying to say is that this kind of
process is better suited for an algorithm, rather than a class. The
algorithm approach has the great advantage that you can more easily and
more efficiently compute different averages (for example with different
set of kickoff/unit/interval/window) on the same set of samples. With
such approach, for example, your code might be written as:
int main()
{
std::multimap<int, double> samples;
samples.insert(std::make_pair(0, 5.0));
samples.insert(std::make_pair(0, 5.0));
samples.insert(std::make_pair(1, 5.0));
samples.insert(std::make_pair(1, 5.0));
samples.insert(std::make_pair(10, 0.0));
std::vector<std::pair results;
// start at 0, unit = 1, interval = 1, window = 10
compute_averages(samples, results, 0, 1, 1, 10);
// ... output part here, omitted for brevity
return 0;
}
or if you prefer a more stl-like iterator-based interface, as I do:
// start at 0, unit = 1, interval = 1, window = 10
compute_averages(samples.begin(), samples.end(),
std::back_inserter(results), 0, 1, 1, 10);
that has the advantage that the source range can come from any sorted
container and not necessarily a multimap. If, for example, you happen to
have a vector of samples, you can just sort them with std::sort and feed
the vector in the algorithm, without copying the sample into a multimap.
Similarly for the target range (however you might probably need a deque
to hold temporary data if you want to perform the computation in a
single pass).
HTH,
Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Irek Szczesniak
Guest
|
| Posted: Sun Nov 13, 2005 10:54 pm Post subject: Re: a class for computing averages |
|
|
Hi Alberto,
| Quote: | I did not look at the detail of your code, but it seems to me that
you are doing more than simple "averages" in there. For example, the
presence of parameters kickoff and interval, for example, is a clear
hint that some logic unrelated to "computing an average" is being
done by the class.
|
Well, now I have to admit that indeed my requirements are quite
specific. It might be hard to find a library that fits my needs.
| Quote: | The algorithm approach has the great advantage that you can more
easily and more efficiently compute different averages (for example
with different set of kickoff/unit/interval/window) on the same set
of samples.
|
Thanks for this idea, an algorithm looks attractive for this task.
However, I have so many measurements that I wouldn't be able to store
them in operating memory to later compute an average with an
algorithm. Therefore I went for a class which computes averages on
the fly, keeps the averages and discards the measurement values. This
just proves your point that my requirements are specific.
Alberto, Niek, Tony, thank you for your posts!
Best,
Irek
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
