Python高效筛选多列表中满足时间窗口重合的时间戳

针对你遇到的长时长、大数量时间戳列表的筛选需求，这里提供一种基于全局排序+滑动窗口的高效实现，替代低效的逐个滑动窗口遍历，核心思路是利用排序后线性扫描统计窗口内的列表覆盖数，时间复杂度远低于传统方法。

核心思路 #

1. 为所有时间戳附带所属列表索引，合并后全局排序，这样可以用线性滑动窗口快速统计任意宽度窗口内覆盖的不同列表数量。
2. 滑动窗口遍历全局排序后的时间戳，当窗口内覆盖≥3个列表时，标记窗口内所有时间戳为需要保留的目标。
3. 最后将标记的时间戳按原列表分组，得到结果。

代码实现（基于Numpy优化） #

import numpy as np

# 原始时间戳数据
timestamps = [
    [0.2, 0.6, 1.5, 4.3],
    [1.1, 1.4, 3.5, 3.6, 7.9],
    [0.1, 0.7, 1.3, 3.7, 12.2, 36.2],
    [1.3, 1.9, 3.8, 4.0, 21.7]
]

WINDOW_WIDTH = 0.2  # 窗口宽度
MIN_LIST_COUNT = 3  # 至少需要覆盖的列表数量

# 1. 预处理：为每个时间戳添加列表索引，合并后排序
global_entries = []
for list_idx, ts_list in enumerate(timestamps):
    # 确保单列表有序（原始数据无序时启用）
    sorted_ts = sorted(ts_list)
    for t in sorted_ts:
        global_entries.append((t, list_idx))

# 转换为Numpy结构化数组，提升排序和遍历效率
global_np = np.array(global_entries, dtype=[('ts', 'float64'), ('list_id', 'int32')])
global_np.sort(order='ts')  # 按时间戳排序

# 2. 滑动窗口统计并标记符合条件的时间戳
total_entries = len(global_np)
is_keep = np.zeros(total_entries, dtype=bool)
left_ptr = 0
list_counter = {}

for right_ptr in range(total_entries):
    current_ts, current_list = global_np[right_ptr]
    # 更新当前列表的元素计数
    list_counter[current_list] = list_counter.get(current_list, 0) + 1

    # 收缩左边界，确保窗口宽度不超过设定值
    while current_ts - global_np[left_ptr]['ts'] > WINDOW_WIDTH:
        left_ts, left_list = global_np[left_ptr]
        list_counter[left_list] -= 1
        if list_counter[left_list] == 0:
            del list_counter[left_list]
        left_ptr += 1

    # 若窗口覆盖足够多列表，标记窗口内所有元素为保留
    if len(list_counter) >= MIN_LIST_COUNT:
        is_keep[left_ptr:right_ptr+1] = True

# 3. 按原列表分组整理结果
result = [[] for _ in timestamps]
for idx in range(total_entries):
    if is_keep[idx]:
        ts, list_id = global_np[idx]
        result[list_id].append(ts)

# 输出结果
for lst in result:
    print(lst)

运行结果 #

[1.5]
[1.4, 3.6]
[1.3, 3.7]
[1.3, 3.8]

效率说明 #

• 时间复杂度：主要来自全局排序的O(M log M)（M为所有时间戳的总数量），滑动窗口遍历为O(M)，远优于传统逐个时间戳检查每个列表的O(M*N log L)（N为列表数，L为单列表长度）。
• 数据量越大，该方法的优势越明显，Numpy的数组操作进一步降低了内存开销和遍历时间。

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