如何检查任何给定集合中是否存在值

Question

假设我有不同的设置(它们必须不同,我不能按照我正在使用的数据类型加入它们):

r = set([1,2,3])
s = set([4,5,6])
t = set([7,8,9])

检查给定变量是否存在于其中的最佳方法是什么？

我在用:

if myvar in r \
   or myvar in s \
   or myvar in t:

但我想知道是否可以通过使用set诸如此类的属性以某种方式减少这种情况union.

以下工作,但我找不到定义多个联合的方法:

if myvar in r.union(s)
   or myvar in t:

我也想知道这个联盟是否会以某种方式影响性能,因为我猜一个临时set将会动态创建.

Answer 1

您可以使用内置任何:

r = set([1,2,3])
s = set([4,5,6])
t = set([7,8,9])
if any(myvar in x for x in [r,s,t]):
    print "I'm in one of them"

any将在返回的第一个条件下短路,True这样你就可以绕过构建一个潜在的巨大的union或检查可能包含的大量集合.

我也想知道这个联盟是否会影响某种程度的表现,因为我猜一个临时的集合将会在飞行中创建.

据wiki.python.com s|t是O(len(s)+len(t))同时查询是O(1).

对于每个n包含l元素的集合,union迭代地构造集合将导致:

a.union(b).union(c).union(d) .... .union(n)

这相当于O(l+l)为a.union(b)和O(2l+2l+l) a.union(b).union(c)等,这些总结到O(n*(n+1)/2)*l).

O(n^2*l) 是二次的并且使得使用集合的性能优势无效.

n组中的查找any将执行O(n)

Answer 2

只需使用任何:

if any(myvar in x for x in  (r,s,t))

查找集是0(1)这样创造了联盟,以检查是否变量是在任何一组是完全没有必要的,而不是简单地使用检查in以any尽快将其短路如找到匹配,并且不产生新的一组.

而且我也想知道这个联盟是否会影响某种程度的表现

是的当然联合集会影响性能,它增加了复杂性,你每次都在创建一个新的集合,O(len(r)+len(s)+len(t))这样你就可以告别使用高效查找集合的真正意义.

所以最重要的是你要保持有效的查找,你必须将它们组合一次,然后将它们保存在内存中创建一个新变量,然后使用它来进行查找,myvar这样初始创建将会进行0(n),0(1)之后将进行查找.

如果你没有每次想要首先创建联合的查找,你将得到长度的线性解决方案,r+s+t -> set.union(*(r, s, t))而不是最坏的三个常量(平均)查找.这也意味着始终添加或删除从/ r,s或添加/删除的新联合集中的任何元素t.

在中等大小的集合上的一些现实时间显示了完全不同:

In [1]: r = set(range(10000))

In [2]: s = set(range(10001,20000))

In [3]: t = set(range(20001,30000))

In [4]: timeit any(29000 in st for st in (r,s,t))
1000000 loops, best of 3: 869 ns per loop  

In [5]: timeit 29000 in r | s | t
1000 loops, best of 3: 956 µs per loop

In [6]: timeit 29000 in reduce(lambda x,y :x.union(y),[r,s,t])
1000 loops, best of 3: 961 µs per loop

In [7]: timeit 29000 in r.union(s).union(t)
1000 loops, best of 3: 953 µs per loop

联盟的时间显示,几乎所有的时间都花在了联合调用上:

In [8]: timeit r.union(s).union(t)
1000 loops, best of 3: 952 µs per loop

使用更大的集合并获取最后一组中的元素:

In [15]: r = set(range(1000000))

In [16]: s = set(range(1000001,2000000))

In [17]: t = set(range(2000001,3000000))


In [18]: timeit any(2999999 in st for st in (r,s,t))
1000000 loops, best of 3: 878 ns per loop

In [19]: timeit 2999999 in reduce(lambda x,y :x.union(y),[r,s,t])
1 loops, best of 3: 161 ms per loop

In [20]: timeit 2999999 in r | s | t
10 loops, best of 3: 157 ms per loop

无论集合使用多大都没有区别,any但随着集合大小的增长,使用union的运行时间也会增长.

使其更快的唯一方法是坚持,or但我们正在采取几百纳秒的差异,这是创建生成器表达式和函数调用的成本:

In [22]: timeit 2999999 in r or 2999999 in s or 2999999 in t
10000000 loops, best of 3: 152 ns per loop

对于联合集set.union(*(r,s,t))也是最快的,因为你不构建中间集:

In [47]: timeit 2999999 in set.union(*(r,s,t))
10 loops, best of 3: 108 ms per loop
In [49]: r | s | t  == set.union(*(r,s,t))
Out[49]: True

Answer 3

|是setspython中的union运算符.您可以使用|as 定义多个集合的并集:

>>> r = set([1,2,3])
>>> s = set([4,5,6])
>>> t = set([7,8,9])
>>> r | s | t
set([1, 2, 3, 4, 5, 6, 7, 8, 9])