Алгоритм сбора итоговых событий за последнее определенное время

Question

У меня проблема с алгоритмом.

У нас есть задача, которая запускается каждые 10 мс, и во время работы событие может произойти или не произойти.Есть ли какой-нибудь простой алгоритм, который позволяет нам отслеживать, сколько раз событие вызывается в течение, скажем, 1 секунды?

Единственная идея, которая у меня есть, - реализовать массив и сохранить все события.,Поскольку мы программируем встраиваемые системы, не хватает места ...

Заранее спасибо.

Answer 1

Это более или менее то, что предложили Dtyree и Weeble, но может помочь пример реализации (пример кода C):

#include <stdint.h>
#include <stdbool.h>

#define HISTORY_LENGTH 100  // 1 second when called every 10ms

int rollingcount( bool event )
{
    static uint8_t event_history[(HISTORY_LENGTH+7) / 8] ;
    static int next_history_bit = 0 ;
    static int event_count = 0 ;

    // Get history byte index and bit mask
    int history_index = next_history_bit >> 3 ;             // ">> 3" is same as "/ 8" but often faster
    uint8_t history_mask = 1 << (next_history_bit & 0x7) ;  // "& 0x07" is same as "% 8" but often faster

    // Get current bit value
    bool history_bit = (event_history[history_index] & history_mask) != 0 ;

    // If oldest history event is not the same as new event, adjust count
    if( history_bit != event )
    {
        if( event )
        {
            // Increment count for 0->1
            event_count++ ;

            // Replace oldest bit with 1
            event_history[history_index] |= history_mask ;
        }
        else
        {
            // decrement count for 1->0
            event_count-- ;

            // Replace oldest bit with 0
            event_history[history_index] &= ~history_mask ;
        }
    }

    // increment to oldest history bit
    next_history_bit++ ;
    if( next_history_bit >= HISTORY_LENGTH ) // Could use "next_history_bit %= HISTORY_COUNT" here, but may be expensive of some processors
    {
        next_history_bit = 0 ;
    }

    return event_count ;
}

Для истории выборки 100 требуется 13 байтов плюс два целых числа статически выделенной памяти, я использовал int для общности, но в этом случае uint8_t счетчиков будет достаточно. Кроме того, есть три переменные стека, и снова использование int не является необходимым, если вам нужно действительно оптимизировать использование памяти. Таким образом, всего можно использовать всего 15 байтов плюс три байта стека. Аргумент event может передаваться или не передаваться в стеке, тогда есть адрес возврата вызова функции, но опять же, это зависит от соглашения о вызовах вашего компилятора / процессора.

Answer 2

массив из 13 байтов для второго события с шагом 10 мс.

Рассмотрим это массив из 104 битов, маркирующих от 0 мс до 104 мс

если событие происходит, отметьте бит и увеличивайте его до следующего раза, иначе просто увеличивайте до следующего бита / байта.

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

Вы можете уменьшить размер массива в соответствии с доступным пространством.

Неясно, могло ли событие произойти несколько раз во время выполнения вашей задачи или между событиями всегда 10 мс.

Answer 3

Будет ли работать следующее приложение для вас?

Счетчик скользящих событий, который увеличивает каждое событие.

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

Это говорит о том, сколько событий произошло в течение окна 10 мс.

Answer 4

Можете ли вы позволить себе массив из 100 логических значений? Возможно, как битовое поле? Пока вы можете позволить себе стоимость места, вы можете отслеживать количество событий в постоянном времени:

1. Магазин:
   1. Счетчик C, изначально 0.
   2. Массив логических значений B, размер которого равен числу интервалов, которые вы хотите отслеживать, т. Е. 100, изначально все ложные.
   3. Индекс I, изначально 0.
2. Каждый интервал:
   1. прочитайте логическое значение в B [i] и уменьшите C, если это правда.
   2. установить для логического значения B [i] значение true, если событие произошло в этом интервале, в противном случае - значение false.
   3. Приращение C, если событие произошло в этом интервале.
3. Когда я достигну 100, сбросьте его на 0.

Таким образом вы, по крайней мере, избегаете сканирования всего массива каждый интервал.

---

РЕДАКТИРОВАТЬ - Итак, вы хотите отслеживать события за последние 3 минуты (180 с, 18000 интервалов). Используя приведенный выше алгоритм и встраивая логические значения в битовое поле, для которого требуется общее хранилище:

2 byte unsigned integer for C
2 byte unsigned integer for I
2250 byte bit-field for B

Это в значительной степени неизбежно, если вам требуется точный подсчет количества событий за последние 180.0 секунд за все время. Я не думаю, что было бы трудно доказать, что вам нужна вся эта информация, чтобы иметь возможность дать точный ответ в любое время. Однако, если бы вы могли знать только количество событий за последние 180 +/- 2 секунды, вы могли бы вместо этого уменьшить разрешение по времени. Вот подробный пример, расширяющий мой комментарий ниже.

Вышеприведенный алгоритм обобщает:

1. Магазин:
   1. Счетчик C, изначально 0.
   2. Массив счетчиков B, размер которого равен числу интервалов, которые вы хотите отслеживать, то есть 100, изначально все 0.
   3. Индекс I, изначально 0.
2. Каждый интервал:
   1. читать B [i] и уменьшать C на эту величину.
   2. записать количество событий, произошедших за этот интервал, в B [i].
   3. Увеличение C на количество событий, произошедших за этот интервал.
3. Когда я достигну длины B, сбросьте ее на 0.

Если вы переключите свой интервал на 2 с, то в это время могут произойти 0-200 событий. Таким образом, каждый счетчик в массиве может быть однобайтовым целым числом без знака. У вас будет 90 таких интервалов в течение 3 минут, поэтому вашему массиву потребуется 90 элементов = 90 байтов.

Если вы переключите свой интервал на 150 мс, то в это время может произойти 0-15 событий. Если вам нужно пробел, вы можете втиснуть это в полубайтовое целое число без знака. У вас будет 1200 таких интервалов за 3 минуты, поэтому вашему массиву потребуется 1200 элементов = 600 байт.

Answer 5

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

Решение кольцевого буфера: (я использовал псевдокод).

Создать встречный массив из 100 счетчиков (изначально заполненных нулями).

int[100] counter_array;
current_counter = 0

В течение цикла 10 мс:

counter_array[current_counter] = 0;   
current_counter++;

Для каждого события:

counter_array[current_counter]++

Чтобы проверить количество событий за последние s, возьмите сумму counter_array