CODEWITHSUNDEEP
python-3.xlistsetset-intersection
Mukesh Jha
Mukesh Jha

Reputation: 175

How to find intersection of 2 lists in least time complexity in python 3.5 excluding the built in set function?

I know we can solve with this method but I am curious to know is there any other method with least time complexity.

a=[1,2,3,4]
b=[2,3,5]
c=set(a).intersection(b)

This gives the answer but is there any shorter method?And it would also be helpful if someone explains what is the time complexity of this built in function in python 3.5

Upvotes: 1

Views: 1513

Answers (1)

wencakisa
wencakisa

Reputation: 5958

Shorter solution:

If you want a shorter method, you can use the & operator for sets, which is exactly an intersection:

>>> a = [1, 2, 3, 4]
>>> b = [2, 3, 5]
>>> c = set(a) & set(b)
{2, 3}

Time complexity:

Python has a module called timeit, which measures execution time of small code snippets. So in your case:

With the intersection() function:

$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a).intersection(set(b))"

100000000 loops, best of 3: 0.00989 usec per loop

With the & operator:

$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a) & set(b)"

100000000 loops, best of 3: 0.01 usec per loop

You see that there is a very small difference between them (because in the inside they are the same thing). But there is no more efficient way of doing set intersection, because the built-in methods are enough optimized.

Here is a table of time complexity of each collection method in Python. Look at the set section:

  • Operation: Intersection s&t
  • Average case: O(min(len(s), len(t))
  • Worst case: O(len(s) * len(t))
  • Notes: replace "min" with "max" if t is not a set

Upvotes: 1

Related Questions