python 中“set.intersection()”的算法是什么？

Question

首先，我的目的是随机获取两个已知集合中的一个元素。所以我原来的方法是首先将两个集合相交。然后从相交集中随机选取一个元素。但这是愚蠢的，因为我只需要一个元素，但需要一个相交的集合。

所以我需要找到set.intersection()的算法。

我比较了“set.intersection()”和“for{for{}}”方法之间的成本时间。 Set.intersection() 比其他方法快（100 倍）。因此，使用“for{for{}}”来随机选取元素并不是一个明智的主意。

Python 中 set.intersection() 背后的算法是什么？

Answer 1

算法如下：循环较小的集合，并根据是否在较大的集合中找到每个元素来复制。所以，它相当于 C 语言

def intersect(a, b):
    if len(a) > len(b):
        a, b = b, a

    c = set()
    for x in a:
        if x in b:
            c.add(x)
    return c

（或：

return set(x for x in a if x in b)

。）

Answer 2

在Python中，您可以通过对两个集合进行按位与来找到两个集合的交集，如下所示：

a & b

，它将返回一个仅包含两个集合元素的新集合，但它使用相同的算法。