如何针对大规模列表快速判断点是否在区间内及实现位置标注

你的当前实现用双层循环逐个比对，在数据量小的时候完全没问题，但一旦feature_info的区间数量或者position_info的位置数量上去（比如成千上万条），O(N*M)的时间复杂度会让运行速度变得很慢。下面给你两种高效的优化方案，适配不同的场景：

方案一：二分查找快速缩小匹配范围 #

先对区间做一次预处理排序，之后用二分查找快速定位可能包含当前位置的区间，只需要检查这些候选区间而不是全部：

import bisect

# 原始数据
feature_info = [[1, 10, 'a'],[15, 30, 'b'],[40, 60, 'c'],[55, 71, 'd'],[73, 84, 'e']]
position_info = {5:'some info', 16:'some other info', 75:'last info'}

# 预处理：按区间起始位置排序，只需要做一次
feature_sorted = sorted(feature_info, key=lambda x: x[0])
# 提取所有区间的起始点，用于二分查找
start_points = [interval[0] for interval in feature_sorted]

# 存储最终标注结果
position_labels = {}

for pos, pos_detail in position_info.items():
    # 用bisect_right找到第一个起始点大于当前位置的索引
    # 索引之前的所有区间都有可能包含当前位置
    candidate_idx = bisect.bisect_right(start_points, pos)
    matched_features = []
    # 只遍历候选区间
    for i in range(candidate_idx):
        s, e, feat = feature_sorted[i]
        if s <= pos < e:
            matched_features.append(feat)
    position_labels[pos] = (pos_detail, matched_features)

print(position_labels)
# 输出结果：{5: ('some info', ['a']), 16: ('some other info', ['b']), 75: ('last info', ['e'])}

为什么这个方案更快？ #

• 排序只需要执行一次，时间复杂度是O(M log M)（M是区间数量）
• 每个位置的匹配步骤：二分查找是O(log M)，之后只需要遍历可能包含该位置的候选区间（数量远小于M），整体时间复杂度降到O(M log M + N(log M + K))，其中K是每个位置实际匹配的区间数，比原始的O(N*M)效率提升非常明显。

方案二：双指针法（适合位置也能排序的场景） #

如果你的位置信息可以先排序，用双指针法能进一步优化，让每个区间和位置都只被遍历一次：

# 原始数据
feature_info = [[1, 10, 'a'],[15, 30, 'b'],[40, 60, 'c'],[55, 71, 'd'],[73, 84, 'e']]
position_info = {5:'some info', 16:'some other info', 75:'last info'}

# 预处理：排序区间和位置
feature_sorted = sorted(feature_info, key=lambda x: x[0])
sorted_positions = sorted(position_info.items(), key=lambda x: x[0])

position_labels = {}
interval_ptr = 0
total_intervals = len(feature_sorted)

for pos, pos_detail in sorted_positions:
    matched_features = []
    # 移动区间指针，找到所有起始点<=当前位置的区间
    while interval_ptr < total_intervals and feature_sorted[interval_ptr][0] <= pos:
        s, e, feat = feature_sorted[interval_ptr]
        if pos < e:
            matched_features.append(feat)
        interval_ptr += 1
    # 注意：如果存在起始点小于当前位置但结束点大于前面区间的情况，不需要往回遍历
    # 因为区间是按起始点排序的，后面的区间起始点更大，不会有遗漏
    position_labels[pos] = (pos_detail, matched_features)

print(position_labels)
# 输出结果和方案一一致

这个方案的优势： #

整体时间复杂度是O(M log M + N log N)，当位置数量N很大时，这个方法的效率会比二分查找更优，因为避免了每个位置的二分查找步骤，全程只做线性遍历。

选择建议 #

• 如果只是偶尔处理小批量数据：你的原始代码简单直接，没必要改
• 如果是大规模数据处理：优先用方案一；如果位置可以排序，方案二更高效

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