Пример среднего значения, полученного за последние X секунд

Question

У меня есть класс, который отправляет события Success и Failure, и мне нужно вести статистику среднего числа отказов / общего количества событий за последние X секунд из этого класса.

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

1. Мне нужно постоянно увеличивать / уменьшать размер списка, чтобы учесть требование «последних X секунд» (количество событий в секунду может изменяться)
2. Мне нужно постоянно просматривать список и подсчитывать все события (потенциально дорого, так как у меня будет 100 таких событий в секунду)

Кто-нибудь знает другой способ вычисления средних значений из списка выборок, полученных за последние X секунд?

Answer 1

Вы должны использовать частоту дискретизации (а-ля MRTG). Допустим, вам нужна точность только в одну секунду, и для поддержания среднего значения за последнюю минуту у вас будет фиксированная таблица из 60 записей, относящихся к прошедшим 60 секундам (включая текущую). А также поддерживать текущую глобальную запись.

Каждая запись состоит из среднего значения и количества событий. Каждая запись начинается с 0 для обоих значений.

Когда вы получаете новое событие, вы изменяете текущую и глобальную запись следующим образом:

average = ((number * average) + 1) / (number + 1)
number = number + 1

В каждом интервале выборки вы изменяете глобальную запись, используя самую старую запись:

global.average = ((global.number * global.average) - (oldest.number * oldest.average)) / (global.number - oldest.number)
global.number = global.number - oldest.number

И вы сбрасываете самую старую запись на 0 и начинаете использовать ее в качестве текущей.

Answer 2

Вы можете использовать очередь , которая позволит вам добавлять новые события в конец очереди и удалять просроченные события из начала очереди, предполагая, что события добавляются в хронологическом порядке. Например, в Java вы можете использовать LinkedList или ArrayDeque, оба из которых реализуют интерфейс Queue.

Если события не добавляются в хронологическом порядке, то можно использовать приоритетную очередь . Элементы будут упорядочены по их временным меткам, а элемент с наивысшим приоритетом (то есть следующий элемент для удаления) будет элементом с наименьшей временной меткой. В Java эта структура данных предоставляется PriorityQueue.

Вместо периодического подсчета событий мы можем просто сохранить два счетчика: один для общего числа событий, а другой для количества успешных событий. Эти счетчики будут обновляться всякий раз, когда мы добавляем или удаляем события из очереди.

Answer 3

Насколько специфичны ваши требования? Если вам позволено мыслить нестандартно, простой алгоритм счетчика Гейгера, или цифровой фильтр с бесконечной импульсной характеристикой (IIR), вычисляет скользящее «среднее» (в зависимости от того, как вы определяете «среднее»), объем памяти и занимает всего несколько строк кода.

Answer 4

Обычно для этих типов сэмплеров вы обычно указываете одну дополнительную вещь: разрешение сэмплера .

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

Если разрешение, которое вы хотите для сэмплера, составляет 1 секунду, то вот предложение алгоритма, которое может работать достаточно хорошо.

• создать связанный список. Узлы списка содержат [метку времени, количество успешных попыток, число ошибок, предыдущий узел]
• сохраняет ссылку на последний узел списка как lastNode, а ссылку на первый узел firstNode (lastNode будет хвостом списка, а firstNode - последний добавленный узел, руководитель)
• содержит две глобальные переменные gSuccess, gFail, сумму успехов и неудач за последние X секунд.

При получении нового события:

• Сравнить событие [отметка времени] с firstNode timestamp

  IF (eventTimestamp.TotalSeconds> firstNode.TotalSeconds)

  • Добавить новый узел a в начале списка (вставить перед firsNode) со счетчиком Succes и Failure 0.
  • firstNode.Previous = newNode
  • firsNode = newNode;

  END IF

  • Увеличить firstNode.Success или firstNode.Failure count на 1
  • * Увеличение gSuccess или gFail на 1

  (после каждого добавленного события) REMOVE_EXPIRED_NODES

• WHILE (lastNode! = Nil AND curentTime.TotalSeconds - lastNode.TotalSeconds> X)

  • gSuccess - = lastNode.Succes (уменьшить gSuccess на удаляемом узле Количество успешных попыток)
  • gFail - = lastNode.Fail (уменьшить gFail на удаляемый узел Количество ошибок)
  • Удалить lastNode

  END WHILE

получению gFail и gSuccess всегда должен предшествовать REMOVE_EXPIRED_NODES.

Преимущества этого подхода:

• Глобальные счетчики для Неудачи и Успеха не пересчитываются из всех событий, а вместо этого постепенно добавляемые события добавляются и уменьшаются при удалении узлов из списка старше X секунд.

• он использует разрешение сэмплера в 1 секунду вместо сохранения списка всех событий (которые могут быть сотнями в секунду, обеспечивая выполнение в общей сложности 2 операций со списками за каждую секунду (операции добавления + удаления))

• , независимо от количества событий, число операций списка в секунду в среднем равно 2 (1 операция добавления, 1 операция удаления)

Answer 5

хранить ваши события в очереди . Просто добавьте в конец и удалите все события, которые слишком стары с фронта. Это как минимум устранит проблему 1.

Answer 6

Было бы более эффективно поддерживать два отдельных списка, один для успехов и один для неудач. Новые записи всегда добавляются в конец списка (то есть сортируются по возрастанию временных меток).

Теперь, когда вы хотите получить количество успехов / неудач за последние n секунд, вы создаете временную метку для now() - n и работаете со списками. Как только вы найдете временную метку, превышающую это значение, вы можете удалить все элементы до текущей. Длина списка дает число успешных или неудачных попыток.

Если вам нужно оптимизировать, посмотрите, эффективнее ли сортировать список, уменьшив временную метку (т.е. добавляя новые значения), и работайте со списком, пока не найдете элемент, у которого временная метка меньше значения сравнения. Откажитесь от этого и всех следующих участников.

Трудно сказать заранее, какой сценарий будет более эффективным, поэтому вам придется попробовать его. OTOH, если он работает достаточно хорошо, нет причин для оптимизации; -).