在 Python 中测试列表重叠

简介

在 Python 中，确定一个列表中的元素是否存在于另一个列表中对于各种数据操作任务至关重要。本文探讨了测试这种重叠的不同方法，评估其效率并提供最佳实践。

方法

1。生成器表达式

any(i in a for i in b)

此方法迭代一个列表并检查另一个列表中的成员资格，如果匹配则返回 True成立。其时间复杂度为 O(n)，其中 n 是较大列表的长度。

2。集合交集

bool(set(a) & set(b))

此方法将两个列表转换为集合并找到它们的交集。如果交集非空，则返回 True。最坏情况的时间复杂度为 O(n m)，其中 n 和 m 是列表的长度。

3。混合集交集

a = set(a)
any(i in a for i in b)

此方法仅将一个列表转换为集合，并迭代另一个列表，检查集合成员资格。它避免了中间集合的创建，使其比传统集合交集更快。

4。 Isdisjoint 方法

not set(a).isdisjoint(b)

该方法使用冻结集合的 isdisjoint 方法来确定它们是否有公共元素。如果不存在，结果为 False；

效率比较

最坏情况：

• 生成器表达式：O(n)
• 集合交集：O(n m)
• 混合集合交集：O(n m)
• 不相交方法：O(1)

大多数情况下，不相交方法是最快的，因为它受益于恒定时间集成员资格检查。

生成器表达式的最佳情况：

• 当列表的前几个元素时重叠。在这种情况下，生成器表达式可以很快返回 True。

需要考虑的因素：

• 列表大小
• 分布列表中的元素
• 共享元素的频率

最佳实践

• 对于小型列表（
• 如果列表结构是可预测的（例如，已排序），则生成器表达式可能会更快。
• 当列表之间存在显着的大小差异时，请使用 isdisjoint 方法，并以较小的列表作为第一个参数。
• 对于共享元素很少或没有的列表，isdisjoint 方法通常更有效。