Как реализовать счетчик, который затухает со временем?

Требования к специальному счетчику

Я хочу реализовать специальный счетчик: все операции инкремента истекают через определенный промежуток времени (скажем, 30 дней).

Пример:

  • День 0: счетчик = 0. TTL = 30 дней
  • День 1: счетчик приращений (+1)
  • День 2: счетчик приращений (+1)
  • День 3: значение счетчика == 2
  • День 31: значение счетчика == 1
  • День 32: значение счетчика == 0

Наивное решение

Наивной реализацией является сохранение набора временных меток, где каждая временная метка равна времени приращения. Значение счетчика равно размеру набора после вычитания всех временных отметок, для которых истекло время ожидания.

Этот наивный счетчик имеет O(n) пространство (размер набора), имеет O(n) поиск и O(1) вставки. Значения точные.

Лучшее решение (для меня)

Обменяйте скорость и память на точность.

Я хочу счетчик с O(1) поиска и вставки, O(1) пробел. Точность <точная.

В качестве альтернативы я бы принял O(log n) пробел и поиск.

Представление счетчика должно подходить для хранения в поле базы данных, т. Е. Я должен иметь возможность быстро обновлять и опрашивать счетчик без чрезмерных (де) издержек сериализации.

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

Как я мог реализовать такой счетчик?

Источник

3 ответа

Решение

Если вы можете жить с 24-часовой детализацией, то вы можете поместить свой счетчик в k блоков, где k - количество дней в вашем самом длинном TTL.

Инкремент - операция O(1) - просто увеличьте значение в сегменте с индексом (k-TTL), а также текущую общую сумму.

Чтение - это еще одна операция O(1), поскольку вы просто читаете текущую итоговую сумму.

Cronjob выскакивает из корзины, срок действия которой истек, каждую ночь (и добавляет корзину со значением 0 на противоположном конце) и уменьшает ваш счетчик на сумму в этой корзине (это фоновая задача, поэтому она не повлияет на операции вставки или чтения)

Источник

Распадающийся счетчик на основе отжига

Вот счетчик, который основан на отжиге (реализован в Python).

  • Счетчик экспоненциально затухает со временем; контролируется скоростью alpha
  • Когда вы читаете и пишете счетчик, вы предоставляете индекс времени (увеличиваете или читаете счетчик в момент времени t)
  • Вы можете прочитать счетчик в настоящем и будущем (по индексу последнего приращения), но не в прошлом
  • Временные индексы последовательных приращений должны быть слабо монотонно возрастающими

Алгоритм является точным по сравнению с альтернативной формулировкой (отжиг против TTL). Имеет приращение O(1) и читает. Он занимает O(1) места, фактически только три поля с плавающей запятой.

class AnnealingCounter():

    def __init__(self, alpha=0.9):
        self.alpha = alpha  # rate of decay
        self.last_t = .0  # time of last increment
        self.heat = .0  # value of counter at last_t

    def increment(self, t=None, amount=1.0):
        """
        t is a floating point temporal index.
        If t is not provided, the value of last_t is used
        """
        if t is None: t = self.last_t
        elapsed = t - self.last_t
        if elapsed < .0 :
            raise ValueError('Cannot increment the counter in the past, i.e. before the last increment')
        self.heat = amount + self.heat * (self.alpha ** elapsed)
        self.last_t = t

    def get_value(self, t=None):
        """
        t is a floating point temporal index.
        If t is not provided, the value of last_t is used
        """
        if t is None: t = self.last_t
        elapsed = t - self.last_t
        if elapsed < .0 :
            raise ValueError('Cannot increment the counter in the past, i.e. before the last increment')
        return self.heat * (self.alpha ** elapsed)

    def __str__(self):
        return str('Counter value at time {}: {}'.format(self.last_t, self.heat))

    def __repr__(self):
        return self.__str__()

Вот как это использовать:

>>> c = AnnealingCounter(alpha=0.9)
Counter has value 0.0 at time 0.0

>>> c.increment()  # increment by 1.0, but don't move time forward
Counter has value 1.0 at time 0.0
>>> c.increment(amount=3.2, t=0.5)  # increment by 3.2 and move time forward (t=0.5)
Counter has value 4.14868329805 at time 0.5
>>> c.increment()  # increment by 1.0, but don't move time forward
Counter has value 5.14868329805 at time 0.5


>>> c.get_value()  # get value as after last increment (t=0.5)
5.148683298050514
>>> c.get_value(t=2.0)
4.396022866630942  # get future value (t=2.0)
Источник

Поскольку приращение истекает в том же порядке, в котором они произошли, отметки времени образуют простую очередь.

Текущее значение счетчика может быть сохранено отдельно в O(1) дополнительной памяти. В начале каждой операции (вставка или запрос), когда срок действия фронта очереди истек, он выталкивается из очереди и счетчик уменьшается.

Обратите внимание, что каждая из n временных меток создается и выводится один раз. Таким образом, у вас есть O(1) амортизированное время для доступа к текущему значению и O(n) памяти для хранения не истекших временных отметок. Фактическое наибольшее использование памяти также ограничено отношением TTL / частоты вставок новой временной метки.

Источник
Другие вопросы по тегам