python - 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)。）