Python isDisjoint() 运行时 [英] Python isDisjoint() runtime
问题描述
Python 2.7 的 isDisjoint(other)
集合方法的算法运行时是什么?比简单地执行 intersection(other)
然后检查返回的交集的 len()>0
是否更快?
两种情况下的复杂度都是 O(min(len(s), len(t))
.唯一的不同之处在于 intersection
创建一组新的所有匹配项,而 isdisjoint
只返回一个布尔值,一旦找到匹配项就可以短路.
立即短路的示例:
<预><代码>>>>s1 = 设置(范围(10**6))>>>s2 = set([0] + list(range((10**6), 2 * (10**6))))>>>s1.intersection(s2)设置([0])>>>%timeit s1.isdisjoint(s2)10000000 个循环,最好的 3 个:每个循环 94.5 ns>>>%timeit s1.intersection(s2)100 个循环,最好的 3 个:每个循环 6.82 毫秒在这种情况下,时间彼此接近,表明在循环过程中很晚才找到匹配的项目.
<预><代码>>>>s1 = 设置(范围(10**6))>>>s2 = set(range((10**6) - 1, 2 * (10**6)))>>>s1.intersection(s2)设置([999999])>>>%timeit s1.isdisjoint(s2)100 个循环,最好的 3 个:每个循环 5.37 毫秒>>>%timeit s1.intersection(s2)100 个循环,最好的 3 个:每个循环 6.62 毫秒What is the algorithmic runtime of Python 2.7's isDisjoint(other)
method for sets? Is it faster than simply doing intersection(other)
and then checking len()>0
of that returned intersection?
The complexity in both cases is going to be O(min(len(s), len(t))
. The only difference is that intersection
creates a new set of all matched items and isdisjoint
simply returns a boolean and can short-circuit as soon as a match is found.
Example that short-circuits right away:
>>> 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
In this case the timings are close to each other, suggesting the matched item was found pretty late during the 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() 运行时的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!