Python快速检查集合a中是否有任何元素在集合b中

Question

我想优化代码，并学习Python的速度（表现）。你能告诉我比较两个集合或字典，看看里面有没有重复项的最快方法吗？

我做了一些研究，但还是不确定这是否是最终的解决方案。

from timeit import Timer
import random

random.seed(1)
x = 10

a = dict(zip(random.sample(range(x), x), random.sample(range(x), x)))
b = dict(zip(random.sample(range(x), x), random.sample(range(x), x)))

def setCompare():
  return len(set(a) & set(b)) > 0

def setDisjointCompare():
  return set(a).isdisjoint(set(b))

def dictCompare():
  for i in a:
    if i in b:
      return False
  return True

print Timer(setCompare).timeit()
print Timer(setDisjointCompare).timeit()
print Timer(dictCompare).timeit()

目前的结果是：

3.95744682634
2.87678853039
0.762627652397

Answer 1

评论里说得对，你的测量方法不一致，我来告诉你为什么。用你现在的代码，我得到了类似的结果：

1.44653701782
1.15708184242
0.275780916214

如果我们把 dictCompare() 改成下面这样：

def dictCompare():
    temp = set(b)
    for i in set(a):
        if i in temp:
            return False
        return True

那么我们得到的结果就变成了：

1.46354103088
1.14659714699
1.09220504761

这次，结果都比较接近（而且都比较慢），因为大部分时间都花在了创建集合上。你在前两种方法中计时的时候包含了集合的创建，而第三种方法则使用了已经存在的对象，这就导致了不一致。

在你的评论中，你提到想排除创建要比较的对象所花的时间。那么我们来用一种一致的方式来做这件事：

# add this below the definitions of a and b
c = set(a)
d = set(b)

# change setCompare and setDisjointCompare()

def setCompare():
    return len(c & d) > 0

def setDisjointCompare():
    return c.isdisjoint(d)

# restore dictCompare() so it matches the OP

现在我们得到的结果是：

0.518588066101
0.196290016174
0.269541025162

通过让三种方法都使用现有的对象，我们让条件变得公平了。前两种方法使用的是现有的集合，第三种方法使用的是现有的字典。现在内置的方法（#2）变成了最快的，这并不让人意外。但要记住，我们在使用它之前必须花时间生成集合，所以即使 isdisjoint() 方法是最快的，如果我们只是想比较字典，单单为了比较而把字典转换成集合，实际上会比第三种方法慢。

不过还有一个选项，和评论中提到的类似：

def anyCompare():
    return not any(k in b for k in a)
# side note: we want to invert the result because we want to return false once
# we find a common element

把这个作为第四种方法添加后，结果是：

0.511568069458
0.196676969528
0.268508911133
0.853673934937

不幸的是，这个方法似乎比其他方法慢，这让我感到惊讶。根据我所知，any() 的工作方式和我们显式循环的短路是一样的（根据文档，所以我不知道为什么我们的显式循环会更快。我怀疑在 any() 调用时短路可能发生得更晚，因为我们在最后反转了结果，而不是在循环中遇到假条件时立即返回。

在这些选项中，dictCompare() 中的显式循环似乎是检查字典中是否有重叠键的最快方法。

顺便提一下，你使用的第一种方法也需要反转结果，以便与其他方法一致，假设你想在有重叠时返回 False，就像 isdisjoint() 那样。