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

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。否则我会实现。