Python isDisjoint() 运行时

Question

isDisjoint(other)Python 2.7 的集合方法的算法运行时间是多少？intersection(other)它比简单地执行然后检查len()>0返回的交集更快吗？

Answer 1

这两种情况的复杂性都是O(min(len(s), len(t))。唯一的区别是intersection创建一组新的所有匹配项并isdisjoint简单地返回一个布尔值，并且一旦找到匹配项就可以短路。

立即短路的示例：

>>> s1 = set(range(10**6))
>>> s2 = set([0] + list(range((10**6), 2 * (10**6))))
>>> s1.intersection(s2)
set([0])
>>> %timeit s1.isdisjoint(s2)
10000000 loops, best of 3: 94.5 ns per loop
>>> %timeit s1.intersection(s2)
100 loops, best of 3: 6.82 ms per loop

在这种情况下，时间彼此接近，表明匹配的项目在循环过程中很晚才找到。

>>> s1 = set(range(10**6))
>>> s2 = set(range((10**6) - 1, 2 * (10**6)))
>>> s1.intersection(s2)
set([999999])
>>> %timeit s1.isdisjoint(s2)
100 loops, best of 3: 5.37 ms per loop
>>> %timeit s1.intersection(s2)
100 loops, best of 3: 6.62 ms per loop