You may not have noticed, but both of the previous
implementations had a small bug. We used
time_t to store the timestamp, which stores an
integral number of seconds. Because of this rounding,
MinuteCount() actually returns somewhere between
59 and 60 seconds worth of data, depending on when exactly you call
For example, if an event happens at
0.99 seconds, that time will get rounded to
t=0 seconds. And if you call
60.1 seconds, it will return the total for events where
t=1,2,3,...60. So that first event will be
missed, even though it’s technically less than a minute ago.
return 59.5 seconds worth of data. And
HourCount() will return 3599.5 seconds worth of
data (a negligible error).
We could fix all this by using a
time with subsecond granularity. But interestingly, most applications
MinuteHourCounter don’t need
that level of accuracy in the first place. We will exploit this fact to
design a new
much faster and uses less space. It’s a trade-off of precision for performance that will be well worth it.
The key idea is to bucket all the events within a small time window together, and summarize those events with a single total. For instance, the events over the past minute could be inserted into 60 discrete buckets, each 1 second wide. The events over the past hour could also be inserted into 60 discrete buckets, each 1 minute wide.
Using the buckets as shown, ...