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).)