算法在过去一段时间

Question

内收集的事件总数我面临的一个算法问题。

我们有运行每隔10ms和运行过程中，一个事件可以发生或没有发生的任务。有没有简单的算法可以让我们跟踪事件在最近1秒钟内触发多少次？

是我唯一的想法就是实现一个数组，并保存所有的事件。正如我们在嵌入式系统编程，没有足够的空间...提前

感谢。

Answer 1

你需要某种形式的列表/队列等，但ringbuffer有可能是最好的性能。 您需要存储100个计数器（在最后一秒内每个时间间隔为10毫秒）和一个当前计数器。

Ringbuffer解决方案： （我使用伪代码）。

创建100个计数器的counter_array（最初用0填充的）。

int[100] counter_array; 
current_counter = 0 

在10毫秒周期：

counter_array[current_counter] = 0; 
current_counter++; 

对于每一个事件：

counter_array[current_counter]++ 

要在过去的支票事件的数量，采取counter_array的总和

Answer 2

你能买得起100个布尔值的数组吗？也许作为一个领域？只要你能负担得起的成本的空间，就可以跟踪恒定的时间事件的数量：

1. 商店：
   1. 的计数器C，最初0
   2. 布尔B的阵列的大小等于你想跟踪的间隔数，即100，最初都是假的。
   3. 索引I，最初0
2. 每个时间间隔：
   1. 阅读在B [i]于布尔，和减量c如果这是真的。
   2. 设置布尔在B [i]于为true，如果发生在这个间隔中的事件，否则为假。
   3. 增量C如果事件发生在这个时间间隔。
3. 当I达到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事件。所以数组中的每个计数器都可以是一个无符号的单字节整数。在3分钟内你会有90个这样的间隔，所以你的数组需要90个元素= 90个字节。

如果将间隔切换为150ms，那么在此期间可能会发生0-15个事件。如果你按下空格键，你可以把它塞进一个半字节的无符号整数。你会在3分钟内有1200个这样的间隔，所以你的数组需要1200个元素= 600个字节。

Answer 3

13个字节的数组，用于10ms步骤中的第二个事件。

考虑它的104位标记0毫秒的阵列，以104MS如果发生事件标记位和增量到下一个时间

，否则只递增到下一个比特/字节。

如果您希望...每秒钟后运行长度编码将事件位卸载到另一个值中。 或......将其视为循环缓冲区，并保持计数可用于查询。 或两者兼有

您可以减小阵列大小以匹配可用空间。

不清楚在任务运行时事件是否会多次发生，或者事件之间总是有10ms。

Answer 4

请问以下工作适合您吗？

滚动事件计数器，可以增加每个事件。

在每10ms运行一次的例程中，将当前事件计数器值与上次运行例程时存储的事件计数器值进行比较。

这会告诉您在10ms窗口期间发生了多少事件。

Answer 5

这是更多或更少什么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个字节加上3个字节的堆栈。 event参数可能会或可能不会传递到堆栈上，然后是函数调用返回地址，但又取决于您的编译器/处理器的调用约定。