如何计算最后一分钟的运行平均流量

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:]

如您所见，我必须为每条记录都这样做，如果我的流量变大，性能就会很糟糕。

我可以使用更好的数据结构或算法来提高性能吗？更进一步，我如何编写测试来验证我的算法？谢谢！

Answer 1

使用 Queue 来保存<traffic, timestamp>对。这timestamp是它被推送到队列的时间（从服务器到达）。跟踪sum队列的流量。当一个新的流量到达并且它的时间戳和 Queue 的前端元素的时间戳相差 1 分钟以上时，从 Queue 中弹出前端。并从总和中减去弹出的流量值。将新流量推入队列并添加到总和。

这样，您的队列就像一个窗口框架，始终保持 1 分钟的流量。并且您正在跟踪总和并且您知道队列大小，因此您可以计算平均值。

空间复杂度为O(maximum traffic can be arrived within 1 minute)。时间复杂度是O(1)为了随时取平均值。

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

注意：不幸的是我不知道 Python。否则我会执行。