c++ - 检索自上次 n 秒以来设置标志的次数的有效方法

Question

我需要跟踪在过去的 n 秒内启用了多少次标记。下面是我可以想出的示例代码。StateHandler 在最后 n(此处为 360)秒内维护事件数组中标志的值。在我的例子中，每秒都会从外部调用更新函数。因此，当我需要知道自上次 360 秒以来它设置了多少次时，我调用 getEnabledInLast360Seconds。是否可以像不对 bool 值使用数组大小​​ n 那样更有效地做到这一点？

#include <map>
#include <iostream>

class StateHandler
{

    bool active[360];
    int index;

public:
    StateHandler() :
        index(0),
        active()
    {
    }

    void update(bool value)
    {
        if (index >= 360)
        {
            index = 0;
        }
        active[index % 360] = value;

        index++;
    }

    int getEnabledInLast360Seconds()
    {
        int value = 0;
        for (int i = 0; i < 360; i++)
        {
            if (active[i])
            {
                value++;
            }
        }
        return value;
    }
};

int main()
{

    StateHandler handler;
    handler.update(true);
    handler.update(true);
    handler.update(true);
    std::cout << handler.getEnabledInLast360Seconds();
}

Answer 1

是的。使用 numberOfOccurrences(0,360) 和 numberOfOccurrences(1,361) 有 359 个常用术语这一事实。所以记住总和，计算常用项，然后计算新的总和。

void update(bool value)
{
    if (index >= 360)
    {
        index = 0;
    }
    // invariant: count reflects t-360...t-1
    if (active[index]) count--;
    // invariant: count reflects t-359...t-1
    active[index] = value;
    if (value) count++;
    // invariant: count reflects t-359...t

    index++;
}

(请注意，if block 重置 index 消除了对模运算符 % 的需要，所以我删除了它)

另一种方法是使用子集和:

subsum[0] = count(0...19)
subsum[1] = count(20...39)
subsum[17] = count(340...359)

现在你每次只需要加18个数字，你可以每20秒完全替换一个加法。