我认为这是一个相当普遍的问题,但我似乎找不到googling的答案(可能有一个更精确的名称,我不知道的问题)
您需要使用“hit()”方法实现一个结构,用于报告命中和hitsInLastSecond | Minute | Hour方法.你有一个毫秒级的定时器.你如何有效地实现？
我的想法是这样的(在psuedo-C)
class HitCounter {
void hit() {
hits_at[Now()] = ++last_count;
}
int hitsInLastSecond() {
auto before_count = hits_at.lower_bound(Now() - 1 * second)
if (before_count == hits_at.end()) { return last_count; }
return last_count - before_count->second;
}
// etc for Minute,Hour
map<time_point,int> hits_at;
int last_count = 0;
};
这是否有效？好吗？更好吗
更新：添加修剪,并切换到一个德克,因为评论：
class HitCounter {
void hit() {
hits.push_back(make_pair(Now(),++last_count));
}
int hitsInLastSecond() {
auto before = lower_bound(hits.begin(),hits.end(),make_pair(Now() - 1 * second,-1));
if (before == hits.end()) { return last_count; }
return last_count - before_count->second;
}
// etc for Minute,Hour
void prune() {
auto old = upper_bound(hits.begin(). hits.end(),make_pair(Now - 1 * hour,-1));
if (old != hits.end()) {
hits.erase(hits.begin(),old)
}
}
deqeue<pair<time_point,int>> hits;
int last_count = 0;
};
解决方法
你所描述的是一个直方图.
使用哈希,如果你打算纳秒精度,会吃掉你的大部分cpu.你可能需要一个环形缓冲区来存储数据.
使用std :: chrono来实现你所需要的时间精度,但是平均每秒钟的命中率似乎是你需要的最高粒度,如果你正在看整体的大局,看起来似乎并不重要,精度是多少.
这是一个部分的,介绍性的例子,介绍你如何去做：
#include <array>
#include <algorithm>
template<size_t RingSize>
class Histogram
{
std::array<size_t,RingSize> m_ringBuffer;
size_t m_total;
size_t m_position;
public:
Histogram() : m_total(0)
{
std::fill_n(m_ringBuffer.begin(),RingSize,0);
}
void addHit()
{
++m_ringBuffer[m_position];
++m_total;
}
void incrementPosition()
{
if (++m_position >= RingSize)
m_position = 0;
m_total -= m_ringBuffer[m_position];
m_ringBuffer[m_position] = 0;
}
double runningAverage() const
{
return (double)m_total / (double)RingSize;
}
size_t runningTotal() const { return m_total; }
};
Histogram<60> secondsHisto;
Histogram<60> minutesHisto;
Histogram<24> hoursHisto;
Histogram<7> weeksHisto;
这是一个天真的实现,它假设你会每秒调用它并增加位置,并将runTotal从一个直方图转换到下一个每个RingSize(所以每60秒,添加secondsHisto.runningTotal到minutesHisto).
希望这将是一个有用的介绍性的起点.
如果要跟踪每秒点击数较长的直方图,可以使用此模型,通过增加环形尺寸,添加第二个总数来跟踪最后N个环形缓冲区条目,以便m_subTotal = sum(m_ringBuffer [m_position – N .. m_position]),类似于m_total的工作方式.
size_t m_10sTotal;
...
void addHit()
{
++m_ringBuffer[m_position];
++m_total;
++m_10sTotal;
}
void incrementPosition()
{
// subtract data from >10 sample intervals ago.
m_10sTotal -= m_ringBuffer[(m_position + RingBufferSize - 10) % RingBufferSize];
// for the naive total,do the subtraction after we
// advance position,since it will coincide with the
// location of the value RingBufferSize ago.
if (++m_position >= RingBufferSize)
m_position = 0;
m_total -= m_ringBuffer[m_position];
}
你不必使这些大小克服这些大小,这只是一个天真的刮擦模型.有各种各样的选择,例如同时增加每个直方图：
secondsHisto.addHit(); minutesHisto.addHit(); hoursHisto.addHit(); weeksHisto.addHit();
每个都独立翻转,所以都有当前的值.将每个组合的大小尽可能地按照您想要的数据返回.