如何高效实现集合的集合间的特定匹配搜索？

核心思路 #

原实现采用嵌套循环遍历，时间复杂度为O(m*n)（m为search的子集数，n为search_base的子集数）。我们可以通过预构建元素到目标子集的映射，将时间复杂度降至O(m + n)，同时让逻辑更简洁严谨。

优化代码 #

def is_match(search, search_base):
    # 先校验数量一致性，不满足直接返回False
    if len(search) != len(search_base):
        return False
    
    # 预建立元素到所属目标子集的映射
    elem_to_bset = {}
    for bset in search_base:
        for elem in bset:
            elem_to_bset[elem] = bset
    
    # 收集匹配到的目标子集并去重
    matched_bsets = set()
    for s_set in search:
        # 提取单元素子集的唯一元素
        elem = next(iter(s_set))
        # 元素无对应目标子集，直接判定不匹配
        if elem not in elem_to_bset:
            return False
        matched_bsets.add(elem_to_bset[elem])
    
    # 验证匹配到的目标子集数量是否与原集合一致（确保每个目标子集都被匹配一次）
    return len(matched_bsets) == len(search_base)

# 测试示例1
search = frozenset([frozenset([1]), frozenset([3])])
search_base = frozenset([frozenset([1, 2]), frozenset([3, 4])])
print(is_match(search, search_base))  # 输出True

# 测试示例2
search2 = frozenset([frozenset(["Vitamin D"]), frozenset(["Sodium"])])
search_base2 = frozenset([frozenset(["Vitamin D", "Vitamin"]), frozenset(["Sodium", "NA"])])
print(is_match(search2, search_base2))  # 输出True

性能与逻辑优势 #

1. 减少重复遍历：仅需遍历一次search_base建立映射，后续每个搜索元素直接查表，避免嵌套循环的重复计算
2. 提前终止判断：一旦发现搜索元素无对应目标子集，立即返回False，无需继续执行后续逻辑
3. 逻辑严谨性：通过去重后的matched_bsets数量校验，确保每个目标子集都被匹配到，完全符合规则要求

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