Python isDisjoint()运行时

这两种情况的复杂性都将是 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