realizacja „trafień w ostatnim [drugiego/minuta/godzina]” struktury danych

Question

myślę, że jest to dość częste pytanie, ale nie wydaje się znaleźć odpowiedź przez googling wokół (może jest bardziej precyzyjna nazwa problemu nie wiem)

trzeba wdrożyć struktury z „hit()” stosowanej metody zgłosić hitem i hitsInLastSecond? | minute | metody godzinę. Masz zegar z dokładnością nanosekundy. Jak skutecznie to wdrożyć?

Moja myśl była mniej więcej tak (w 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; 
}; 

to działa? Czy to jest dobre? Czy coś jest lepsze?

Aktualizacja: Dodano przycinanie i włączony do deque jak za komentarze:

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

Answer 1

co opisujesz jest nazywany histogramem.

Używając skrótu, jeśli zamierzają nanosekund dokładność, zje się dużo CPU. Prawdopodobnie potrzebujesz bufora pierścieniowego do przechowywania danych.

Użyj std :: chrono, aby osiągnąć wymaganą precyzję pomiaru czasu, ale szczerze mówiąc, trafienia na sekundę wydają się być najlepszą ziarnistością, jakiej potrzebujesz i jeśli patrzysz na ogólny obraz, nie wydaje się, żeby to było strasznie ważne jaka jest precyzja.

To jest częściowa, próbka wprowadzająca jak można go o to:

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

Jest to naiwny realizacja która zakłada można nazwać każdy drugi i zwiększyć pozycję, a transpozycji runningTotal z jednego histogram do następnego każdego rozmiaru pierścienia (więc co 60 sekund, dodaj secondsHisto.runningTotal do minutesHisto).

Mam nadzieję, że będzie to przydatne miejsce wprowadzające zacząć od.

Jeśli chcesz śledzić dłuższy histogram uderzeń na sekundę, możesz to zrobić w tym modelu, zwiększając rozmiar pierścienia, dodaj drugą sumę, aby śledzić ostatnie wpisy N w buforze pierścieniowym, tak aby m_subTotal = sum (m_ringBuffer [m_position - N .. m_position]), podobnie jak działa 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]; 
} 

Nie musisz tworzyć histogramów tych rozmiarów, to po prostu naiwny model skrobania. Istnieją różne alternatywy, takie jak zwiększany każdego histogramu w tym samym czasie:

secondsHisto.addHit(); 
minutesHisto.addHit(); 
hoursHisto.addHit(); 
weeksHisto.addHit(); 

Każdy przewraca niezależnie, więc wszyscy mają aktualne wartości. Wielkość każdego histo, o ile chcesz, aby dane o tej ziarnistości powróciły.