如何读取日志元素计算5分钟（300秒）区间内最大资源请求量

现有24小时窗口内所有resource请求的日志，时间单位为seconds，日志结构示例如下：

log = [
    ['10', 'user_9', 'resource_10'],
    ['123', 'user_5', 'resource_9'],
    ['234', 'user_1', 'resource_3'],
    ['299', 'user_2', 'resource_3'],
    ['594', 'user_1', 'resource_1'],
    ['10293', 'user_8', 'resource_12'],
]
# 预期返回结果：4 [resource_10, resource_9, resource_3, resource_3]

需要遍历日志，找到max数量的、5分钟（300秒）区间内打开的resource。此前尝试遍历列表仅捕获满足150 <= x <= 150的元素，无法捕获与x差值大于150、小于300的元素。目前思路是使用O(n²)的双重循环实现，对应伪代码如下：

遍历日志中的第一个元素（按时间维度）
    将当前元素赋值为currItem
    再次遍历整个列表
        检查每个元素与currItem的时间差是否在300以内
            保存符合条件的元素
    重复上述流程

是否有更高效的实现方案，无需n²次遍历即可得到结果？

可以使用滑动窗口算法，时间复杂度仅为O(nlogn)，远优于O(n²)的暴力方案，实现逻辑如下：

• 第一步：先把所有日志按时间戳从小到大排序，注意要把字符串格式的时间转成整数类型
• 第二步：初始化左右两个指针left=0，最大计数max_count=0，对应区间的资源列表max_resources=[]
• 第三步：遍历右指针，每移动一次右指针，就判断当前右指针对应的时间和左指针对应的时间差是否超过300：
  • 如果超过300，就把左指针向右移动，直到时间差<=300
  • 如果没超过，就计算当前窗口内的元素数量，要是比之前的max_count大，就更新max_count和对应的资源列表
• 第四步：遍历完成后直接返回max_count和对应的资源列表即可

代码示例（Python） #

def find_max_resources_in_5min(logs):
    # 转换时间为int后按时间排序
    sorted_logs = sorted(logs, key=lambda x: int(x[0]))
    left = 0
    max_count = 0
    max_res = []
    n = len(sorted_logs)
    for right in range(n):
        right_time = int(sorted_logs[right][0])
        # 调整左边界，保证窗口时间差不超过300秒
        while right_time - int(sorted_logs[left][0]) > 300:
            left += 1
        # 更新最大计数和对应资源列表
        current_count = right - left + 1
        if current_count > max_count:
            max_count = current_count
            max_res = [item[2] for item in sorted_logs[left:right+1]]
    return max_count, max_res

# 测试示例
log = [
    ['10', 'user_9', 'resource_10'],
    ['123', 'user_5', 'resource_9'],
    ['234', 'user_1', 'resource_3'],
    ['299', 'user_2', 'resource_3'],
    ['594', 'user_1', 'resource_1'],
    ['10293', 'user_8', 'resource_12'],
]
print(find_max_resources_in_5min(log)) # 输出 (4, ['resource_10', 'resource_9', 'resource_3', 'resource_3'])

方案优势 #

• 排序的时间复杂度是O(nlogn)，滑动窗口遍历整个列表是O(n)，整体复杂度远低于暴力双重循环的O(n²)，日志量越大性能优势越明显
• 不需要额外存储大量中间子集，空间复杂度为O(n)（仅存储排序后的列表和结果）

内容的提问来源于stack exchange，提问作者William Merritt