Внедрение "хитов в последней [второй/минута/час]" структуре данных

Я думаю, что это довольно распространенный вопрос, но, похоже, я не могу найти ответ путем поиска по сайту (может быть, есть более точное имя для проблемы, которую я не знаю?)

Вам нужно реализовать структуру с методом "hit()", используемым для сообщения о хитах и ​​методах hitInLastSecond | Minute | Hour. У вас есть таймер с точностью до наносекунды. Как вы эффективно реализуете это?

Моя мысль была чем-то вроде этого (в psuedo-С++)

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;
};

Это работает? Это хорошо? Что-то лучше?

Обновление: добавлена ​​обрезка и переключена на deque в соответствии с комментариями:

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;
};

Ответы

Ответ 1

То, что вы описываете, называется гистограммой.

Использование хэша, если вы намереваетесь наносекундную точность, будет поглощать большую часть вашего процессора. Вероятно, вам нужен буфер для хранения данных.

Используйте 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;

Это наивная реализация, которая предполагает, что вы будете называть ее каждую секунду и увеличивать позицию, и будет транспонировать runningTotal с одной гистограммы на следующую каждый 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();

Каждый катится независимо, поэтому все имеют текущие значения. Размер каждого гистона, если вы хотите, чтобы данные в этой гранулярности возвращались назад.