Как бы сделать умнее (по расходу памяти, ну и может по константам) чем:

import time
from collections import deque

class FpsCounter:
    def __init__(self, XX):
        self._time_window = XX
        self._q = deque()
        self._cnt = 0

    def _trim_queue(self):
        q = self._q

        while q and q[0] < time.time() - self._time_window:
            q.popleft()
            self._cnt -= 1

    def event_happened(self):
        self._q.append(time.time())
        self._cnt += 1

        self._trim_queue()

    def get_count(self):
        self._trim_queue()
        return self._cnt

# Запоминаем события в очередь — увеличиваем счетчик cnt. В методе _trim_queue выкидываем все старые события, счетчик декрементируем.

Здравствуйте, ioctl, Вы писали:

I>Как бы сделать умнее (по расходу памяти, ну и может по константам) чем:

Относительно недавно обсуждали эту задачу здесь же.
Было предложено несколько решений, со своими плюсами и минусами.

I># Запоминаем события в очередь — увеличиваем счетчик cnt. В методе _trim_queue выкидываем все старые события, счетчик декрементируем.

Счетчик не нужен. deque умеет len() за O(1)

P.S. Найти обсуждение сходу не смог, кто-то на собеседовании такую задачу получил.

Здравствуйте, ioctl, Вы писали:

I>Как бы сделать умнее (по расходу памяти, ну и может по константам) чем:

Если вам нужно именно точное значение — то умнее никак.
Если нужно приблизительное значение, то см., например, Скользящее среднее:

import time
import math

class FpsCounter:
    def __init__(self, XX):
        self._time_window = XX
        self._last_time = time.time()
        self._cnt = 0.

    def event_happened(self):
        self._cnt = self.get_count() + 1.
        self._last_time = time.time()

    def get_count(self):
        return self._cnt * math.exp( (   self._last_time - time.time() ) / self._time_window )

O(1) по памяти.

Здравствуйте, ioctl, Вы писали:

I>Как бы сделать умнее (по расходу памяти, ну и может по константам) чем:

Во, нашел
http://rsdn.org/forum/alg/7911204.1

Автор: n0dwis
Дата: 23.12.20

Из простых решений (оптимальных по времени и памяти) — учет событий по "календарным" секундам.
Памяти требуется столько, на сколько секунд хотим видеть назад. Точность подсчета немного падает.

Здравствуйте, ioctl, Вы писали:

I>Как бы сделать умнее (по расходу памяти, ну и может по константам) чем:

Есть несколько разных подходов, со своими плюсами и минусами. Скользящее среднее уже упомянули, я ещё могу добавить про "циклический буффер" — счётчики событий размещаются в виде длинного вектора значений, с нужной гранулярностью. Т.е. если считаем по секундам, то каждая ячейка соответствует одной секунде. Дальше инкрементим счётчики в соответствующей ячейке, когда приходят события. Тут только надо не забыть обнулять новую ячейку, когда переходим к следующей секунде.

Расход памяти — по одной ячейке вектора на каждую секунду, т.е. примерно XX * 4 байт.

Из минусов — гранулярность. На основе всех этих счётчиков потом либо графики строятся, либо реализуются какие-нибудь лимиты. При гранулярности в 1 секунду мы можем получить пик событий, который придётся на вторую половину одной секунду и на первую половину следующей, но на графиках оно поделится пополам.

Здравствуйте, Artem Korneev, Вы писали:

AK>Из минусов — гранулярность. На основе всех этих счётчиков потом либо графики строятся, либо реализуются какие-нибудь лимиты. При гранулярности в 1 секунду мы можем получить пик событий, который придётся на вторую половину одной секунду и на первую половину следующей, но на графиках оно поделится пополам.
Частоту Найквиста никто не отменял, да. Так что потом на графиках binning данных и разрешение должны быть уже с 2 секундами.