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