O'Reilly logo

The Art of Readable Code by Trevor Foucher, Dustin Boswell

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Attempt 3: A Time-Bucketed Design

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 it.

For example, if an event happens at time = 0.99 seconds, that time will get rounded to t=0 seconds. And if you call MinuteCount() at time = 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.

On average, MinuteCount() will 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 using a MinuteHourCounter don’t need that level of accuracy in the first place. We will exploit this fact to design a new MinuteHourCounter that’s 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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required