如何计算过去一分钟的平均流量？

Question

我有一个可以接受时间序列数据的Python服务器。现在，我需要计算最近一分钟的平均流量，输出结果为每分钟90个样本。目前，我正在使用Python列表来保存所有时间戳，并且使用了一种相当糟糕的方法（在我看来）来进行计算。代码大致如下：

class TrafficCalculator(object):
    timestamps = []

    def run():
        while True:
            # this gets one record of traffic
            data = self.accept_data()
            # get record's timestamp
            timestamp = data.timestamp
            # add to list
            self.timestamps.append(timestamp)
            # get the time one minute ago
            minute_ago = timestamp - datetime.timedelta(minutes=1)
            # find out the first index of the timestamp in the past that's within 1 minute
            for i, t in enumerate(self.timestamp):
                if t > minute_ago:
                    break
            # see how many records are within last minute
            result = len(self.timestamp[i:])
            # throw away the earlier data
            self.timestamp = self.timestamp[i:]

如你所见，我必须对每条记录都这样做，如果我的流量变得很大，性能就会很差。

有没有更好的数据结构或算法可以让这个过程更高效？甚至更进一步，怎么编写测试来验证我的算法？谢谢！

- Shang Wang

---

为什么不使用类似pandas这样的东西呢？ - Bahrom

你尝试过每次函数被调用时递增一个int，然后每分钟清除一次吗？要测试你的类，你只需要启动一个脚本，用随机数据攻击self.accept_data()。 - Menachem Hornbacher

Answer 1

使用队列来存储<traffic, timestamp>对。这里timestamp是被推送到队列上的时间（从服务器到达）。跟踪队列中流量的总和。当新的流量到达且它的时间戳与队列前面元素的时间戳之差超过1分钟时，从队列顶部弹出。从总和中减去弹出的流量值。将新流量推入队列并添加到总和中。

通过这种方式，你的队列始终作为窗口框架来保存一分钟的流量。你正在跟踪总和并知道队列大小，因此可以计算平均值。

空间复杂度为O(1分钟内可能到达的最大流量)。任何时候获取平均值的时间复杂度为O(1)。

这是一种非常传统的算法，用于在恒定的时间复杂度内查询任何运行数据流。

注意：很遗憾，我不知道Python。否则我会提供实现。

- Kaidul

---

谢谢，你不懂Python但我懂编程，所以没关系。但同时我也有点难过，因为这很明显。 - Shang Wang

不客气。有时候我们会错过一些非常明显的东西 :) - Kaidul

Answer 2

你可以通过以下方式实现：

• 定义一个长度为90（样本/分钟）的向量（或列表）data
• 有一个指针p=0
• 有一个变量sum（尚未初始化）

使用前90个样本填充向量；计算总和并将其放入变量sum中。

然后：

• 从sum中减去data[p]（从总和中删除最旧的样本）
• 读取下一个样本并将其放置在位置p的向量中 （因此擦除最旧的数据）；
• 将新的data[p]添加到sum中（当前总和）
• 将指针p增加1；如果p>=90，则再次p=0 （p指向最旧的可用数据）
• 当前平均值为sum/90

等等。

- Thomas Baruchel