c - 一段时间内随机事件的数量

Question

我需要跟踪给定时间段内随机事件的数量。我可以检测到事件的最大速率是每秒一次，我需要能够提供过去 30 分钟内的事件数。

我对该算法的第一个破解是拥有一个数组，该数组将保存以秒为单位的时间戳。每次发生新事件时，所有时间戳都向下移动，新事件放在数组的前面。当请求事件数时，我会删除所有超过 30 分钟的事件，然后返回结果计数。

time_t event_stamps[60 * 30];
unsigned event_count;

void events_put()
{
    time_t new_event_time = SomeCallToGetTheCurrentTimeInSeconds();

    /* Shift values down the array to make space for the new value at index 0 */
    int i;
    for(i = sizeof(event_stamps) / sizeof(event_stamps[0]); --i > 0; )
    {
        event_stamps[i] = event_stamps[i-1];
    }

    event_stamps[0] = new_event_time;

    if(event_count < sizeof(event_stamps) / sizeof(event_stamps[0]))
    {
        event_count++;
    }   
}

uint32_t events_get(void)
{
    time_t systime_s = SomeCallToGetTheCurrentTimeInSeconds();

    /* Remove elements in the array that are occurred greater than 30 minutes ago */
    int i;
    for(i = event_count; --i >= 0; )
    {
        /* Events arrive in order so events further away in time occur at higher array
         * indices. Therefore, once an event is reached that is sooner than the cutoff
         * time (30 minutes * 60 seconds), there are no more events to remove */
        if(systime_s - event_stamps[i] <= (30 * 60))
        {
            break;
        }

        event_count--;
    }

    return event_count;
}

不用说，这个数组非常大(60 * 30 = 1800 个元素 * 4 = 7200 B)并且不适合我的小处理器。有没有一种方法可以在不使用那么多数据空间的情况下跟踪这些事件？

Answer 1

使用以秒为索引的循环位数组:1800 位，持续 30 秒。

记录上次事件时间。

设置适当的位并记录事件发生的时间，但首先清除前一个事件时间和现在之间的所有位。

上报事件个数时，先清空前一个事件时间到现在的所有位，然后统计位。