如何高效移除元组列表中存在包含关系的部分重复项？

嘿，这个问题我之前碰到过类似场景，要快速解决的话，得先抓住核心逻辑：我们要保留的是那些没有被任何其他元组完全覆盖的元组——简单来说，如果元组X的每一个非空元素，在另一个元组Y的对应位置都有相同的值，而且Y还有更多非空元素，那X就该被移除，留下Y这种“更完整”的条目。

核心判断规则 #

对于两个元组t1和t2，t1被t2覆盖的条件是：

• 对于每一个位置j，如果t1[j]不是空字符串''，那么t2[j]必须等于t1[j]
• 因为题目说明所有元组唯一，所以t2至少有一个位置是填充值，而t1对应位置是空（否则两个元组完全相等，不符合唯一条件）

高效实现思路 #

直接两两比较所有元组的时间复杂度是O(M²*N)（M是列表长度，N是元组长度），虽然M=1000时也能跑，但我们可以通过两个优化点大幅提升速度：

1. 按非空元素数量降序排序：非空元素越多的元组，越不可能被其他元组覆盖，反而更可能覆盖别人。先处理这些元组，后续只需要检查新元组是否被已保留的元组覆盖即可。
2. 掩码快速过滤：把每个元组的非空位置转换成二进制掩码（比如N=4时，('A','B','','')的掩码是0b1100即12），如果t1的掩码不是t2掩码的子集（t1_mask & t2_mask != t1_mask），那t1肯定不会被t2覆盖，直接跳过元素比较。

代码实现 #

基础版本（易理解）

def filter_tuples(tuple_list):
    # 按非空元素数量从多到少排序
    sorted_list = sorted(tuple_list, key=lambda t: -sum(1 for x in t if x != ''))
    filtered = []
    for current in sorted_list:
        # 检查当前元组是否被已保留的任意元组覆盖
        is_covered = False
        for candidate in filtered:
            covered = True
            for curr_val, cand_val in zip(current, candidate):
                # 如果当前元组有非空值，但候选元组对应位置不一样，就不满足覆盖
                if curr_val != '' and curr_val != cand_val:
                    covered = False
                    break
            if covered:
                is_covered = True
                break
        if not is_covered:
            filtered.append(current)
    return filtered

# 测试示例
sample_list = [('A', 'B', '', ''), ('A', 'B', 'C', ''), ('', '', '', 'D'), ('A', '', '', 'D'), ('', 'B', '', '')]
print(filter_tuples(sample_list))  # 输出: [('A', 'B', 'C', ''), ('A', '', '', 'D')]

优化版本（更快，适合大列表）

通过掩码和预处理非空键值对，减少不必要的元素比较：

def filter_tuples_optimized(tuple_list):
    if not tuple_list:
        return []
    tuple_length = len(tuple_list[0])
    # 预处理每个元组：(负非空数用于排序, 掩码, 非空位置-值列表, 原元组)
    processed = []
    for t in tuple_list:
        non_empty_pairs = [(idx, val) for idx, val in enumerate(t) if val != '']
        non_empty_count = len(non_empty_pairs)
        # 生成掩码：每个非空位置对应二进制位为1
        mask = sum(1 << idx for idx, _ in non_empty_pairs)
        processed.append((-non_empty_count, mask, non_empty_pairs, t))
    
    # 按非空元素数量降序排序（负数值升序等价于原数降序）
    processed.sort()
    filtered = []
    # 保存已保留元组的掩码和非空键值对，用于快速判断
    candidate_data = []
    
    for _, curr_mask, curr_non_empty, curr_tuple in processed:
        is_covered = False
        for cand_mask, cand_non_empty in candidate_data:
            # 先判断掩码是否是子集，不是的话直接跳过
            if (curr_mask & cand_mask) != curr_mask:
                continue
            # 再检查所有非空位置的值是否匹配
            match = True
            for idx, val in curr_non_empty:
                # 找到候选元组对应位置的值
                cand_val = next((v for i, v in cand_non_empty if i == idx), '')
                if val != cand_val:
                    match = False
                    break
            if match:
                is_covered = True
                break
        if not is_covered:
            filtered.append(curr_tuple)
            candidate_data.append((curr_mask, curr_non_empty))
    return filtered

# 测试示例
sample_list = [('A', 'B', '', ''), ('A', 'B', 'C', ''), ('', '', '', 'D'), ('A', '', '', 'D'), ('', 'B', '', '')]
print(filter_tuples_optimized(sample_list))  # 输出同样正确

性能说明 #

• 排序阶段时间复杂度是O(M log M)
• 过滤阶段，因为我们按非空数量排序，且用掩码快速过滤，实际比较次数远小于O(M²*N)，对于M=1000、N=10的场景，完全可以在毫秒级完成计算。

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