Python isDisjoint() 运行时

Question

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

Answer 1

两种情况下的复杂度都将是 O(min(len(s), len(t))。唯一的区别是 intersection 创建一组新的所有匹配项，而 isdisjoint 只是 returns 一个布尔值，并且可以在找到匹配项后立即短路。

马上短路的例子：

>>> 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

Python isDisjoint() 运行时

Python isDisjoint() runtime

python

runtime

set