3

我有一个调度成功和失败事件的类，我需要维护该类最后 X 秒内失败的平均数/事件总数的统计信息。

我正在考虑使用循环链表并为每个事件附加一个成功或失败节点。然后计算列表中故障节点的数量与总节点的数量，但这有两个主要缺点：

  1. 我需要不断扩大/缩小列表大小以考虑“最后 X 秒”的要求（每秒的事件数可以改变）
  2. 我需要不断循环列表并计算所有事件（可能很昂贵，因为我每秒可能会有 100 个此类事件）

有谁知道从最后 X 秒内收到的样本列表中计算平均值的另一种方法？

4

6 回答 6

7

您应该使用采样频率（a-la MRTG）。假设您只需要一秒的精度并保持过去一分钟的平均值，您将有一个固定的表，其中包含 60 个条目，指的是过去 60 秒（包括现在的）。并且还保持当前的全局条目。

每个条目由一个平均值和一些事件组成。两个值的每个条目都从 0 开始。

当您收到一个新事件时，您可以像这样更改当前条目和全局条目：

平均值 = ((数字 * 平均值) + 1) / (数字 + 1)
数字 = 数字 + 1

在每个采样间隔，您使用最旧的条目更改全局条目：

global.average = ((global.number * global.average) - (oldest.number * old.average)) / (global.number - old.number)
global.number = global.number - old.number

然后您将最旧的条目重置为 0 并开始将其用作当前条目。

于 2009-02-17T10:15:01.037 回答
5

您可以使用queue，这将允许您将新事件添加到队列的末尾，并从队列的开头删除过期的事件，假设事件是按时间顺序添加的。例如，在 Java 中，您可以使用 aLinkedList或 an ArrayDeque，它们都实现了Queue接口。

如果事件未按时间顺序添加，则可以使用优先级队列。元素将按其时间戳排序，最高优先级元素（即下一个要删除的元素）将是具有最小时间戳的元素。在 Java 中，此数据结构由PriorityQueue.

我们可以只保留两个计数器，而不是定期计算事件，一个用于事件总数，另一个用于成功事件的数量。每当我们从队列中添加或删除事件时，这些计数器都会更新。

于 2009-02-17T10:10:07.307 回答
1

将您的事件保存在Queue中。只需追加到末尾并从前面删除所有太旧的事件。这至少会消除问题 1。

于 2009-02-17T10:07:09.543 回答
1

通常对于这些类型的采样器，您通常会指定一件事，那就是采样器分辨率。

在您的情况下，假设您的描述，采样器分辨率可以是 1 秒或 1 滴答声。

如果您想要的采样器分辨率是 1 秒，那么这里有一个可能运行良好的算法命题。

  • 创建一个链表。列表节点保存 [timestamp, Success count, Failure count, previousNode]
  • 存储对列表最后一个节点的lastNode引用和对第一个节点的引用firstNode（lastNode将是列表的尾部，并且firstNode是最新添加的节点，头部）
  • 包含两个全局变量 gSuccess、gFail，最后 X 秒时间范围内成功和失败的总和。

收到新事件时：

  • 将事件 [timestamp] 与 firstNode 进行比较timestamp

    IF (eventTimestamp.TotalSeconds > firstNode.TotalSeconds)

    • 在列表的开头添加一个新节点 a（插入到 firsNode 之前），成功和失败计数为 0。
    • firstNode.Previous = newNode
    • 第一节点 = 新节点；

    万一

    • 将 firstNode.Success 或 firstNode.Failure 计数增加 1
    • *将 gSuccess 或 gFail 增加 1

    （添加每个事件后）REMOVE_EXPIRED_NODES

  • WHILE ( lastNode != nil AND currentTime.TotalSeconds - lastNode.TotalSeconds > X)

    • gSuccess -= lastNode.Succes（按要删除的节点减少 gSuccess 成功计数）
    • gFail -= lastNode.Fail（按要删除的节点减少 gFail 失败计数）
    • 删除最后一个节点

    结束时

获取 gFail 和 gSuccess 应该始终在 REMOVE_EXPIRED_NODES 之前。

这种方法的优点：

  • Fail 和 Success 的全局计数器不会从所有事件中重新计算，而是添加逐渐递增的事件，并在删除列表中早于 X 秒的节点时递减。

  • 它使用 1 秒的采样器分辨率，而不是存储所有事件的列表（可能每秒数百次，确保每秒执行总共 2 个列表操作（添加 + 删除操作））

  • 无论事件数量如何，平均每秒列表操作计数为 2（1 个添加操作，1 个删除操作）

于 2009-02-17T11:29:03.810 回答
1

您的要求有多具体？如果允许您跳出框框思考，一个简单的盖革计数器算法，也就是无限脉冲响应 (IIR) 数字滤波器计算移动“平均值”（取决于您如何定义“平均值”），具有最小内存占用，只需要几行代码。

于 2009-02-17T17:37:49.163 回答
0

维护两个单独的列表会更有效，一个用于成功，一个用于失败。新条目总是附加在列表的末尾（即按增加的时间戳排序）。

现在，当您想获得最后 n 秒内的成功/失败次数时，您可以为now() - n列表创建一个时间戳并对其进行处理。一旦找到大于该值的时间戳，就可以消除当前元素之前的所有元素。列表的长度为您提供成功或失败的次数。

如果您需要优化，请查看通过减少时间戳（即添加新值）对列表进行排序是否更有效，并处理列表直到找到时间戳小于比较值的元素。丢弃此成员和所有以下成员。

很难事先说哪种方案会更有效，因此您必须尝试一下。OTOH 如果它工作得足够好，就没有理由优化 ;-)。

于 2009-02-17T10:11:32.187 回答