python中'set.intersection()'的算法是什么?

2022-01-17 00:00:00 python algorithm set intersection set-intersection

问题描述

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

First of all, my purpose is to randomly get only one element in both known sets. So my original method is firstly intersect two sets. And then randomly pick up a element from the intersected set. But this is foolish, because that I only need a elements but a intersected set.

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

So I need to find the algorithm of set.intersection().

我比较了 'set.intersection()' 和 'for{for{}}' 方法的成本时间.Set.intersection() 比其他更快(100 倍).所以使用'for{for{}}'来随机选取一个元素并不是一个明智的主意.

I compare the cost time between the methods of 'set.intersection()' and 'for{for{}}'. Set.intersection() is more faster than other one(100 times). So using 'for{for{}}' to pick up a randomly elements is not a wise idea.

python 中 set.intersection() 背后的算法是什么?

What's the algorithm behind set.intersection() in python?

解决方案

算法如下:循环遍历较小的集合，并根据是否在较大的集合中找到每个元素来复制每个元素.所以，它是 C 的等价物

The algorithm is as follows: the smaller set is looped over and every element is copied depending whether it's found in the bigger set. So, it's the C equivalent of

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

相关文章