如何高效从大型Python整数列表中识别特定事件？

需求明确 #

给定大型整数列表，需找出所有满足以下条件的元素索引：

• 元素值严格大于指定数值 S
• 该元素之前存在在上一次同类事件之后出现的零（零无需紧邻当前元素）

以示例为例：

S=6，列表 List = [3, 5, 6, 0, 2, 5, 6, 8, 3, 0, 7]
符合条件的索引为7和10：

• 索引7的元素8>6，此前索引3的零在首次事件前存在
• 索引10的元素7>6，此前索引9的零在上一次事件（索引7）之后出现

方案1：Numpy向量化实现（适合超大型列表） #

利用Numpy的底层C实现快速定位目标元素，再通过双指针遍历匹配条件，时间复杂度为O(M+N)（M为大于S的元素数，N为零的数量），效率远高于纯Python遍历。

import numpy as np

def find_event_indices(arr, S):
    arr = np.array(arr)
    # 批量获取所有零的索引
    zero_indices = np.where(arr == 0)[0]
    # 批量获取所有大于S的元素索引
    gt_S_indices = np.where(arr > S)[0]
    
    event_indices = []
    last_event_idx = -1
    zero_ptr = 0  # 指针追踪有效零的位置
    zero_count = len(zero_indices)
    
    for idx in gt_S_indices:
        # 跳过在上一次事件之前的零
        while zero_ptr < zero_count and zero_indices[zero_ptr] <= last_event_idx:
            zero_ptr += 1
        # 检查是否存在当前元素之前的有效零
        if zero_ptr < zero_count and zero_indices[zero_ptr] < idx:
            event_indices.append(idx)
            last_event_idx = idx
    
    return event_indices

# 测试示例
List = [3, 5, 6, 0, 2, 5, 6, 8, 3, 0, 7]
print(find_event_indices(List, 6))  # 输出: [7, 10]

方案2：优化的纯Python循环（无需依赖第三方库） #

仅遍历列表一次，实时追踪上一次事件位置和上一次有效零位置，时间复杂度O(n)，对于百万级以内的列表足够高效。

def find_event_indices_py(lst, S):
    event_indices = []
    last_event_idx = -1
    last_valid_zero_idx = -1  # 记录上一次事件之后出现的零的位置
    
    for idx, num in enumerate(lst):
        if num == 0:
            # 更新有效零位置（仅当零在上一次事件之后）
            if idx > last_event_idx:
                last_valid_zero_idx = idx
        elif num > S:
            # 检查当前元素是否满足条件：有效零在上一次事件之后且在当前元素之前
            if last_valid_zero_idx > last_event_idx and last_valid_zero_idx < idx:
                event_indices.append(idx)
                last_event_idx = idx
    
    return event_indices

# 测试示例
List = [3, 5, 6, 0, 2, 5, 6, 8, 3, 0, 7]
print(find_event_indices_py(List, 6))  # 输出: [7, 10]

方案选择 #

• 若列表规模达到千万级以上，优先选择Numpy方案，利用其向量化操作的性能优势
• 若无需依赖第三方库，或列表规模中等，优化后的纯Python循环足够高效且更轻量

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