CODEWITHSUNDEEP
pythonalgorithmsetintersectionset-intersection
Ding Ding
Ding Ding

Reputation: 306

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

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.

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

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.

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

Upvotes: 11

Views: 6888

Answers (2)

Arjun
Arjun

Reputation: 1

In python, you can find the intersection of two sets by just taking the bitwise AND of both sets like this: a & b, and it will return a new set with only the elements of both, but it uses the same algorithm.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363587

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

(Or: return set(x for x in a if x in b).)

Upvotes: 16

Related Questions