如何在Python中快速查找包含指定元素集合的子列表索引

需求为编写Python代码，当目标列表中的所有数字均存在于某个子列表（同一行）时，返回该子列表的索引。但当前实现的代码在处理大型列表时运行速度极慢，原代码如下：

numbers = [[1, 3, 5, 7, 12, 14, 19, 21, 26, 31, 42, 44, 48, 53, 54, 58, 59, 61, 62, 78],
        [4, 6, 8, 11, 16, 19, 22, 27, 28, 33, 38, 45, 46, 52, 53, 54, 61, 70, 71, 77],
        [1, 4, 5, 7, 11, 16, 31, 33, 37, 44, 46, 49, 53, 59, 62, 64, 68, 70, 73, 78],
        [5, 7, 8, 15, 19, 20, 27, 35, 41, 42, 45, 51, 53, 55, 60, 66, 68, 72, 77, 80],
        [3, 14, 18, 21, 25, 26, 29, 36, 43, 44, 45, 53, 55, 56, 61, 62, 64, 66, 71, 72],
        [2, 7, 10, 12, 16, 24, 34, 40, 42, 43, 46, 51, 52, 53, 56, 57, 60, 65, 72, 79],
        [6, 7, 11, 14, 18, 25, 30, 34, 47, 52, 53, 57, 62, 65, 67, 68, 71, 72, 77, 78],
        [1, 2, 3, 7, 9, 16, 20, 26, 27, 30, 32, 35, 38, 48, 54, 63, 64, 65, 69, 72],
        [3, 8, 10, 15, 19, 20, 34, 40, 44, 48, 51, 52, 56, 58, 62, 66, 69, 70, 76, 77],
        [3, 7, 13, 17, 24, 28, 31, 36, 37, 39, 48, 50, 52, 58, 59, 61, 63, 64, 74, 79]]


find = [[7, 16, 20],
        [7, 16, 42],
        [7, 16, 52],
        [7, 50, 52]]



def searchForCombinations(combinations_list, results_list):
    
    for sublist_index, results_sublist in enumerate(results_list):
        for  combinations_index, combinations_sublist in enumerate(combinations_list):
            if not combinations_sublist in results_sublist:
                break
            else:
                if combinations_index == len(combinations_list) - 1:
                    return sublist_index
                    break
             
resultIndex = []
for i, combSublist in enumerate(find):
    resultIndex.append(searchForCombinations(combSublist, numbers))
    
resultIndex.sort(reverse=True)



print(resultIndex)

原代码性能瓶颈 #

• 列表的in操作时间复杂度为O(n)，每次检查目标数字是否在子列表中都要遍历整个子列表，大型数据下会产生大量重复计算。
• 嵌套循环层级过多，每个目标组合都要遍历所有子列表，再逐个检查目标数字，整体时间复杂度为O(MNK)（M为目标组合数，N为子列表数，K为目标组合的长度）。

优化方案：用集合加速成员检查 #

通过将子列表转换为集合，利用集合O(1)的成员检查特性，结合子集判断方法，大幅提升查询效率。

优化后代码 #

numbers = [[1, 3, 5, 7, 12, 14, 19, 21, 26, 31, 42, 44, 48, 53, 54, 58, 59, 61, 62, 78],
        [4, 6, 8, 11, 16, 19, 22, 27, 28, 33, 38, 45, 46, 52, 53, 54, 61, 70, 71, 77],
        [1, 4, 5, 7, 11, 16, 31, 33, 37, 44, 46, 49, 53, 59, 62, 64, 68, 70, 73, 78],
        [5, 7, 8, 15, 19, 20, 27, 35, 41, 42, 45, 51, 53, 55, 60, 66, 68, 72, 77, 80],
        [3, 14, 18, 21, 25, 26, 29, 36, 43, 44, 45, 53, 55, 56, 61, 62, 64, 66, 71, 72],
        [2, 7, 10, 12, 16, 24, 34, 40, 42, 43, 46, 51, 52, 53, 56, 57, 60, 65, 72, 79],
        [6, 7, 11, 14, 18, 25, 30, 34, 47, 52, 53, 57, 62, 65, 67, 68, 71, 72, 77, 78],
        [1, 2, 3, 7, 9, 16, 20, 26, 27, 30, 32, 35, 38, 48, 54, 63, 64, 65, 69, 72],
        [3, 8, 10, 15, 19, 20, 34, 40, 44, 48, 51, 52, 56, 58, 62, 66, 69, 70, 76, 77],
        [3, 7, 13, 17, 24, 28, 31, 36, 37, 39, 48, 50, 52, 58, 59, 61, 63, 64, 74, 79]]

find = [[7, 16, 20],
        [7, 16, 42],
        [7, 16, 52],
        [7, 50, 52]]

# 预处理：将所有子列表转换为集合并保存索引，仅执行一次
number_sets = [(idx, set(sublist)) for idx, sublist in enumerate(numbers)]

result_index = []
for target in find:
    target_set = set(target)
    # 遍历预处理后的集合，检查目标集合是否是子列表集合的子集
    for idx, s in number_sets:
        if target_set.issubset(s):
            result_index.append(idx)
            break  # 找到第一个符合条件的索引立即停止

result_index.sort(reverse=True)
print(result_index)

优化说明 #

1. 预处理集合：一次性将所有子列表转换为集合并关联索引，避免后续重复转换操作。
2. 子集判断：使用集合的issubset()方法直接判断目标数字集合是否包含于子列表集合，比逐个检查数字更高效。
3. 提前终止遍历：找到符合条件的子列表索引后立即跳出循环，减少不必要的遍历。

内容的提问来源于stack exchange，提问作者Iulian T.