如何确定一个事件的速率（移动平均）是否超过了阈值。

Question

编辑 添加信息

原本这只是一个通用的算法，不关注语言/平台。然而我将自己回答这个问题，并且答案实际上与正在使用的工具有关。

这是针对在IBM主机下z/OS上使用Ops/MVS自动化工具运行REXX脚本进行事件检测的，所以发布的答案可能适用于Python、Perl、bash、Java等各种语言；只是这种产品在这种特定情况下有一个特定的功能可以解决问题。

添加信息结束

我的问题与以下问题非常相似:

如何基于事件时间计算连续平滑事件率？

这将是一个答案：

这可以通过移动平均实现。取您的最后N个事件，其中N是您平均窗口的大小。计算这些N个事件之间的时间差。如果您以秒为单位测量并希望以分钟为单位获得速率，则应将60秒除以以秒表示的时间差，然后乘以N-1。

但我想避免存储有关先前事件的信息。我只对平均移动速率是否超过阈值感兴趣，因此不关注速率趋势。

例如，我想知道是否每分钟有3次以上的事件。以下是我的第一种方法:

1. 当第一个事件发生时，我创建一个计数器，记录开始时间。
2. 当另一个事件发生时，我增加计数并根据计数和经过的时间计算速率。
3. 如果速率超过允许的值，则生成警报。

我意识到这不起作用，因为如果您在一周前有一个事件，然后直到最近一分钟内出现10个事件，平均速率是一周内的11个，即3.6/天，而不是当前速率为10个/分钟。

所以我想尝试以下内容:

1. 当第一个事件发生时，我创建一个计数器，记录开始时间。
2. 当另一个事件发生时，如果自上一个事件以来的时间超过我想要测量速率的间隔（在我的例子中为1分钟），我有效地丢弃先前的事件，并将计数器设置为1，将当前时间记录为新的开始时间（因为如果自上一个事件以来已经超过了1分钟，速率不能超过x/min，对吧？）
3. 如果自上一个事件以来的时间没有超过监测间隔，则增加计数并从计数和经过的时间计算速率。
4. 如果速率超过允许的值，则生成警报。

这似乎很简单，但SO上的其他帖子（特别是这个问题：使用指数平滑和不规则事件估算事件发生率以及它的被接受的答案：https://dev59.com/jmAg5IYBdhLWcg3waKZ2#23617678）似乎暗示着比我想象中更复杂。

- Steve Ives

---

这个回答解决了你的问题吗？实时计算服务器在最近一分钟内的访问次数的高效方法。如果没有，你可能需要澄清你所说的“移动平均”是什么意思（任何形式的平均都会导致你的示例未触发10的阈值）。 - Bernhard Barker

@Dukeling，它可能有效，但我使用的语言（在IBM大型机上的Ops/MVS REXX）不支持数组。自从问了这个问题后，我发现Ops/MVS有一个内置函数可以执行此任务。我不知道是否应该扩展我的答案以包括这些细节，然后回答它，还是只需删除该问题。 - Steve Ives

我认为你需要澄清一下这是在早期使用Ops/MVS；如果是这种情况，我会保留这个问题，因为它非常具体，而且不是通过其他问题得到了答案。 - Kevin McKenzie

@KevinMcKenzie同意了 - 我已经移动了它。 - Steve Ives

Answer 1

Ops/MVS内置了“OPSTHRSH”功能，可以实现此功能：

https://docops.ca.com/ca-opsmvs/13-5/en/reference-information/command-and-function-reference/ops-rexx-built-in-functions/opsthrsh-function

针对这种特定情况，我们可以按照以下方式调用它：

if OPSTHRSH('A',60) > 3 then do something...

OPSTHRESH('A',60)将返回当前地址空间（任务）在60秒内触发当前事件的次数。如果此值超过我的触发级别，则采取行动。在收到第一个事件后60秒，事件计数将被重置。

- Steve Ives

Answer 2

使用以下伪代码：

boolean update(long timestamp, History h, int windowSize, int minEventsToTrigger) {
    h.removeOlderThan(timestamp - windowSize);
    h.addEvent(timestamp);
    return h.size() >= minEventsToTrigger;
}

其中h是一个循环缓冲区，用于存储时间戳，并具有以下操作：

• removeOlderThan(t)：删除所有在t之前发生的事件。该操作的平摊复杂度为O(1)，因为每个事件仅被删除一次，并且（除最旧的事件外）事件不会被多次查询以进行删除。

• addEvent(t)：在缓冲区末尾添加事件，如果缓冲区已满，则首先删除最旧的事件，然后再添加新事件。该操作的复杂度为O(1)；并且通过舍弃旧事件以获得新事件，可以保证突发事件不会使系统过载、需要额外的内存或破坏此代码——只要minEventsToTrigger小于h的容量，结果将始终正确。

我相信这段伪代码在时间上是最优的，可能也是空间上最优的。重要的是，它不需要任何动态分配。

update 函数会在给定新事件的情况下，如果在 windowSize 时间单位内接收到至少 minEventsToTrigger 个事件，则返回 true；否则返回 false。请注意，它旨在仅在每个事件接收时被调用，因此只能准确检测 上升沿（下降沿将无法被检测直到下一个事件）。如果您想纠正这一点，您有两个选项：

• 定期轮询以查看是否满足条件 return h.size() >= minEventsToTrigger;，在调用 h.removeOlderThan(timestamp - windowSize); 后不再成立。如果事件非常少见，这可能是浪费的；如果只在触发警报时执行此操作，则可以节省大量不必要的操作。
• 使用某种定时器机制，在触发警报后，恰好在最老的事件过期后醒来。这将保证事件过期和检查 h.size() >= minEventsToTrigger 之间的最小延迟。

- tucuxi

---

我不想存储关于先前事件的信息（尽可能地），因为我使用的语言缺乏数组等功能。 - Steve Ives

如果您只想在1分钟内检测到3个事件，那么您可以使用3个时间戳（timestamp）；您不需要一个数组，但是需要3个读/写内存位置。算法是相同的。 - tucuxi