如何高效实现基于秒级边界的固定时长滑动窗口数据提取？

问题描述 #

给定升序排列的秒级时间列表：

L = [0.10218048, 1.20851996, 1.46800021, 1.73429061, 2.71525848, 3.14781922, 3.63637958, 5.11147358, 5.97497864, 6.35469013, 6.80623747, 6.99571917, 7.65215123, 7.86108352, 8.52988247, 8.83068894, 10.07690977, 11.53867284, 12.01214112, 12.13307653]

需要从每个以整数秒为起始、时长可自定义的滑动窗口中提取所有落入窗口的时间值（示例窗口时长为2秒），如何高效实现？

核心思路 #

因为时间列表是升序排列的，我们可以利用这个特性避免暴力遍历每个窗口的所有元素，而是用二分查找或双指针来快速定位每个窗口的左右边界，大幅降低时间复杂度。

方案1：二分查找法（简单易实现） #

利用Python内置的bisect模块，通过二分查找快速找到每个窗口内元素的起始和结束索引，适合大多数场景。

import bisect

def sliding_window_time_extraction(time_list, window_duration):
    # 先确保时间列表是升序的，若输入无序则先排序
    sorted_times = sorted(time_list)
    max_time = sorted_times[-1]
    start_times = []
    
    # 生成所有窗口起始点：从0开始，每次滑动1秒，直到窗口覆盖最大时间
    current_start = 0
    while current_start + window_duration <= max_time + 1e-9:  # 处理浮点精度误差
        start_times.append(current_start)
        current_start += 1
    
    result = []
    for s in start_times:
        end = s + window_duration
        # 找到第一个 >= 窗口起始时间s的元素索引
        left_idx = bisect.bisect_left(sorted_times, s)
        # 找到第一个 >= 窗口结束时间end的元素索引
        right_idx = bisect.bisect_left(sorted_times, end)
        # 提取窗口内的所有元素
        result.append(sorted_times[left_idx:right_idx])
    
    return result

# 测试示例
L = [0.10218048, 1.20851996, 1.46800021, 1.73429061, 2.71525848, 3.14781922, 3.63637958, 5.11147358, 5.97497864, 6.35469013, 6.80623747, 6.99571917, 7.65215123, 7.86108352, 8.52988247, 8.83068894, 10.07690977, 11.53867284, 12.01214112, 12.13307653]
window_duration = 2
output = sliding_window_time_extraction(L, window_duration)
for window in output:
    print(window)

关键点说明：

• 排序步骤：如果输入列表已经是升序的，可以直接跳过，节省O(n log n)的时间
• 浮点精度：加1e-9是为了避免因为浮点数的精度误差，漏掉最后一个可能的窗口
• 时间复杂度：排序O(n log n) + 每个窗口二分查找O(log n)，总复杂度为O(n log n + m log n)，其中m是窗口数量

方案2：双指针法（极致高效） #

因为窗口是按顺序滑动的（起始时间从0到max_time递增），我们可以用双指针逐步移动，避免重复查找，时间复杂度进一步降低到O(n log n + m)，适合处理超大时间列表。

def sliding_window_time_extraction_two_pointers(time_list, window_duration):
    sorted_times = sorted(time_list)
    n = len(sorted_times)
    max_time = sorted_times[-1]
    start_times = []
    
    current_start = 0
    while current_start + window_duration <= max_time + 1e-9:
        start_times.append(current_start)
        current_start += 1
    
    result = []
    left = 0  # 左指针初始位置
    
    for s in start_times:
        end = s + window_duration
        # 移动左指针到第一个 >= 窗口起始时间s的位置
        while left < n and sorted_times[left] < s:
            left += 1
        # 移动右指针到第一个 >= 窗口结束时间end的位置
        right = left
        while right < n and sorted_times[right] < end:
            right += 1
        # 提取窗口元素
        result.append(sorted_times[left:right])
    
    return result

优势：

双指针只会向右移动，不会回溯，整个过程中左右指针总共移动O(n)次，比二分查找更高效，尤其是当窗口数量m很大的时候。

自定义窗口时长 #

只需要修改window_duration参数即可，比如改成3秒，就会生成每个时长为3秒的滑动窗口，完全适配需求。

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