Как найти пересечение двух списков python

Here’s some Python 2 / Python 3 code that generates timing information for both list-based and set-based methods of finding the intersection of two lists.

The pure list comprehension algorithms are O(n^2), since in on a list is a linear search. The set-based algorithms are O(n), since set search is O(1), and set creation is O(n) (and converting a set to a list is also O(n)). So for sufficiently large n the set-based algorithms are faster, but for small n the overheads of creating the set(s) make them slower than the pure list comp algorithms.

#!/usr/bin/env python

''' Time list- vs set-based list intersection
    See http://stackoverflow.com/q/3697432/4014959
    Written by PM 2Ring 2015.10.16
'''

from __future__ import print_function, division
from timeit import Timer

setup = 'from __main__ import a, b'
cmd_lista = '[u for u in a if u in b]'
cmd_listb = '[u for u in b if u in a]'

cmd_lcsa = 'sa=set(a);[u for u in b if u in sa]'

cmd_seta = 'list(set(a).intersection(b))'
cmd_setb = 'list(set(b).intersection(a))'

reps = 3
loops = 50000

def do_timing(heading, cmd, setup):
    t = Timer(cmd, setup)
    r = t.repeat(reps, loops)
    r.sort()
    print(heading, r)
    return r[0]

m = 10
nums = list(range(6 * m))

for n in range(1, m + 1):
    a = nums[:6*n:2]
    b = nums[:6*n:3]
    print('nn =', n, len(a), len(b))
    #print('nn = %dn%s %dn%s %d' % (n, a, len(a), b, len(b)))
    la = do_timing('lista', cmd_lista, setup) 
    lb = do_timing('listb', cmd_listb, setup) 
    lc = do_timing('lcsa ', cmd_lcsa, setup)
    sa = do_timing('seta ', cmd_seta, setup)
    sb = do_timing('setb ', cmd_setb, setup)
    print(la/sa, lb/sa, lc/sa, la/sb, lb/sb, lc/sb)

output

n = 1 3 2
lista [0.082171916961669922, 0.082588911056518555, 0.0898590087890625]
listb [0.069530963897705078, 0.070394992828369141, 0.075379848480224609]
lcsa  [0.11858987808227539, 0.1188349723815918, 0.12825107574462891]
seta  [0.26900982856750488, 0.26902294158935547, 0.27298116683959961]
setb  [0.27218389511108398, 0.27459001541137695, 0.34307217597961426]
0.305460649521 0.258469975867 0.440838458259 0.301898526833 0.255455833892 0.435697630214

n = 2 6 4
lista [0.15915989875793457, 0.16000485420227051, 0.16551494598388672]
listb [0.13000702857971191, 0.13060092926025391, 0.13543915748596191]
lcsa  [0.18650484085083008, 0.18742108345031738, 0.19513416290283203]
seta  [0.33592700958251953, 0.34001994132995605, 0.34146714210510254]
setb  [0.29436492919921875, 0.2953648567199707, 0.30039691925048828]
0.473793098554 0.387009751735 0.555194537893 0.540689066428 0.441652573672 0.633583767462

n = 3 9 6
lista [0.27657914161682129, 0.28098297119140625, 0.28311991691589355]
listb [0.21585917472839355, 0.21679902076721191, 0.22272896766662598]
lcsa  [0.22559309005737305, 0.2271728515625, 0.2323150634765625]
seta  [0.36382699012756348, 0.36453008651733398, 0.36750602722167969]
setb  [0.34979605674743652, 0.35533690452575684, 0.36164689064025879]
0.760194128313 0.59330170819 0.62005595016 0.790686848184 0.61710008036 0.644927481902

n = 4 12 8
lista [0.39616990089416504, 0.39746403694152832, 0.41129183769226074]
listb [0.33485794067382812, 0.33914685249328613, 0.37850618362426758]
lcsa  [0.27405810356140137, 0.2745978832244873, 0.28249192237854004]
seta  [0.39211201667785645, 0.39234519004821777, 0.39317893981933594]
setb  [0.36988520622253418, 0.37011313438415527, 0.37571001052856445]
1.01034878821 0.85398540833 0.698928091731 1.07106176249 0.905302334456 0.740927452493

n = 5 15 10
lista [0.56792402267456055, 0.57422614097595215, 0.57740211486816406]
listb [0.47309303283691406, 0.47619009017944336, 0.47628307342529297]
lcsa  [0.32805585861206055, 0.32813096046447754, 0.3349759578704834]
seta  [0.40036201477050781, 0.40322518348693848, 0.40548801422119141]
setb  [0.39103078842163086, 0.39722800254821777, 0.43811702728271484]
1.41852623806 1.18166313332 0.819398061028 1.45237674242 1.20986133789 0.838951479847

n = 6 18 12
lista [0.77897095680236816, 0.78187918663024902, 0.78467702865600586]
listb [0.629547119140625, 0.63210701942443848, 0.63321495056152344]
lcsa  [0.36563992500305176, 0.36638498306274414, 0.38175487518310547]
seta  [0.46695613861083984, 0.46992206573486328, 0.47583580017089844]
setb  [0.47616910934448242, 0.47661614418029785, 0.4850609302520752]
1.66818870637 1.34819326075 0.783028414812 1.63591241329 1.32210827369 0.767878297495

n = 7 21 14
lista [0.9703209400177002, 0.9734041690826416, 1.0182771682739258]
listb [0.82394003868103027, 0.82625699043273926, 0.82796716690063477]
lcsa  [0.40975093841552734, 0.41210508346557617, 0.42286920547485352]
seta  [0.5086359977722168, 0.50968098640441895, 0.51014018058776855]
setb  [0.48688101768493652, 0.4879908561706543, 0.49204087257385254]
1.90769222837 1.61990115188 0.805587768483 1.99293236904 1.69228211566 0.841583309951

n = 8 24 16
lista [1.204819917678833, 1.2206029891967773, 1.258256196975708]
listb [1.014998197555542, 1.0206191539764404, 1.0343101024627686]
lcsa  [0.50966787338256836, 0.51018595695495605, 0.51319599151611328]
seta  [0.50310111045837402, 0.50556015968322754, 0.51335406303405762]
setb  [0.51472997665405273, 0.51948785781860352, 0.52113485336303711]
2.39478683834 2.01748351664 1.01305257092 2.34068341135 1.97190418975 0.990165516871

n = 9 27 18
lista [1.511646032333374, 1.5133969783782959, 1.5639569759368896]
listb [1.2461750507354736, 1.254518985748291, 1.2613379955291748]
lcsa  [0.5565330982208252, 0.56119203567504883, 0.56451296806335449]
seta  [0.5966339111328125, 0.60275578498840332, 0.64791703224182129]
setb  [0.54694414138793945, 0.5508568286895752, 0.55375313758850098]
2.53362406013 2.08867620074 0.932788243907 2.76380331728 2.27843203069 1.01753187594

n = 10 30 20
lista [1.7777848243713379, 2.1453688144683838, 2.4085969924926758]
listb [1.5070111751556396, 1.5202279090881348, 1.5779800415039062]
lcsa  [0.5954139232635498, 0.59703707695007324, 0.60746097564697266]
seta  [0.61563014984130859, 0.62125110626220703, 0.62354087829589844]
setb  [0.56723213195800781, 0.57257509231567383, 0.57460403442382812]
2.88774814689 2.44791645689 0.967161734066 3.13413984189 2.6567803378 1.04968299523

Generated using a 2GHz single core machine with 2GB of RAM running Python 2.6.6 on a Debian flavour of Linux (with Firefox running in the background).

These figures are only a rough guide, since the actual speeds of the various algorithms are affected differently by the proportion of elements that are in both source lists.

В этом уроке мы обсудим, как мы можем получить пересечение двух списков в Python. Пересечение двух списков означает, что нам нужно добавить все знакомые элементы в оба начальных списка.

Python известен своей превосходной встроенной структурой данных. Список Python – один из самых известных и ценных встроенных типов данных. Он может хранить значения различных типов данных в отсортированном порядке. Однако для списков, таких как наборы, нет встроенной функции.

Вход :

 
list1 = [40, 90, 11, 58, 31, 66, 28, 54, 79] 
list2 = [58, 90, 54, 31, 45, 11, 66, 28, 26] 

Выход:

[90, 11, 58, 31, 66, 28, 54] 

Вход :

 
list1 = [4, 9, 1, 17, 11, 26, 28, 54, 69] 
list2 = [9, 9, 74, 21, 45, 11, 63, 28, 26] 

Выход:

[9, 11, 26, 28] 

Давайте рассмотрим следующие способы, чтобы получить пересечение двух списков.

Способ 1: использование цикла for

 
# Python program to get the intersection 
# of two lists in most simple way 
def intersection_list(list1, list2): 
   list3 = [value for value in list1 if value in list2] 
   return list3 
 
# Driver Code 
list1 = [40, 90, 11, 58, 31, 66, 28, 54, 79] 
list2 = [58, 90, 54, 31, 45, 11, 66, 28, 26] 
print(intersection_list(list1, list2)) 

Выход:

[90, 11, 58, 31, 66, 28, 54] 

Мы использовали цикл for, чтобы получить общее значение из обоих списков и сохранить его в переменной list3.

Способ 2: преобразование списка в набор

 
def intersection_list(list1, list2): 
   return list(set(list1) & set(list2)) 
 
list1 = [40, 90, 11, 58, 31, 66, 28, 54, 79] 
list2 = [58, 90, 54, 31, 45, 11, 66, 28, 26] 
 
print(intersection_list(list1, list2)) 

Выход:

[66, 90, 11, 54, 58, 28, 31] 

Способ – 3: с помощью метода intersection()

Мы воспользуемся встроенным методом intersection(). intersection() – это первоклассная часть множества. Давайте разберемся в следующем примере.

Пример –

 
# Python program to get the intersection 
# of two lists using set() and intersection() 
def intersection_list(list1, list2): 
   return set(list1).intersection(list2) 
 
list1 = [40, 90, 11, 58, 31, 66, 28, 54, 79] 
list2 = [58, 90, 54, 31, 45, 11, 66, 28, 26] 
 
print(intersection_list(list1, list2)) 

Выход:

{66, 90, 11, 54, 58, 28, 31} 

Способ 4: использование гибридного метода

В этом способе мы будем использовать гибридный метод. Он очень эффективен для выполнения данной задачи.

Пример –

 
# Python program to get the intersection 
# of two lists 
def intersection(list1, list2): 
 
   # Use of hybrid method 
   temp = set(list2) 
   list3 = [value for value in list1 if value in temp] 
   return list3 
 
list1 = [40, 90, 11, 58, 31, 66, 28, 54, 79] 
list2 = [58, 90, 54, 31, 45, 11, 66, 28, 26] 
print(intersection(list1, list2)) 

Выход:

[90, 11, 58, 31, 66, 28, 54] 

Способ 5: применение метода filter()

В данном способе мы будем использовать метод filter(). Пересечение выполняется над подсписками внутри других списков. Давайте разберемся в следующем примере.

Пример –

 
# Python program togetthe intersection 
# of two lists, sublists and use of filter() 
def intersection_list(list1, list2): 
   list3 = [list(filter(lambda x: x in list1, sublist)) for sublist in list2] 
   return list3 
 
 
list1 = [10, 9, 17, 40, 23, 18, 56, 49, 58, 60] 
list2 = [[25, 17, 23, 40, 32], [1, 10, 13, 27, 28], [60, 55, 61, 78, 15, 76]] 
print(intersection_list(list1, list2)) 

Выход:

[[17, 23, 40], [10], [60]] 

Метод filter() берет каждый элемент подсписка и проверяет, присутствует ли он в списке1. Понимание списка выполняется для каждого подсписка в list2.

Intersection of two list means we need to take all those elements which are common to both of the initial lists and store them into another list. Now there are various ways in Python, through which we can perform the Intersection of the lists. 
Examples: 
 

Input : 
lst1 = [15, 9, 10, 56, 23, 78, 5, 4, 9]
lst2 = [9, 4, 5, 36, 47, 26, 10, 45, 87]
Output :
[9, 10, 4, 5]

Input :
lst1 = [4, 9, 1, 17, 11, 26, 28, 54, 69]
lst2 = [9, 9, 74, 21, 45, 11, 63, 28, 26]
Output :
[9, 11, 26, 28]

Method 1: 
This is the simplest method where we haven’t used any built-in functions. 
 

Output: 
 

[9, 11, 26, 28]

Method 2: 
This method includes the use of set() method. 
 

Output: 
 

[9, 10, 4, 5]

The time complexity of the above program is O(n), where n is the length of the longer list between lst1 and lst2.

The space complexity of the program is O(n), where n is the length of the smaller list between lst1 and lst2. 

Method 3: 
In this method we set() the larger list and then use the built-in function called intersection() to compute the intersected list. intersection() is a first-class part of set. 
 

Output: 
 

{9, 11}

Method 4: 
By the use of this hybrid method the complexity of the program falls to O(n). This is an efficient way of doing the following program. 
 

Output: 
 

[9, 9, 11]

Method 5: 
This is the where the intersection is performed over sub-lists inside other lists. Here we have used the concept of filter(). 
 

Working: The filter part takes each sublist’s item and checks to see if it is in the source list. The list comprehension is executed for each sublist in list2. 
Output: 
 

[[13, 32], [7, 13, 28], [1, 6]]

Method 6: Using reduce():
Algorithm:

1. Import the reduce function from functools module.
2. Define two lists.
3. Initialize the variable intersection with an empty list.
4. Use the reduce function to iterate over the elements of lst1.
5. Inside the lambda function, check if the current element is present in lst2 and not already present in the intersection list.
6. If it is, then add the current element to the intersection list.
7. Return the intersection list.
8. Print the intersection list.

Time Complexity: O(n^2), where n is the length of lst1.
Space Complexity: O(n), where n is the length of lst1.
 

Last Updated :
23 Apr, 2023

Like Article

Save Article

List is a data type in python which is used to store multiple items. Lists are very versatile because they can store items of multiple types such as integer, string, float, etc. They are mutable, and commas separate their elements. The elements inside a list can be accessed with the help of indexing. In this article, we will be looking into several ways to perform python list intersection.

What is intersection?

An intersection in python can be performed between two or more lists or sets. With intersection, we get the common elements present in all the lists, i.e., it returns the elements which exist in all the lists.

Example : If we have two lists – A and B containing the following elements:

A = [0,1,10,5,8]

B = [7,1,3,11,0]

Then here, there are only two common elements from both the list – 0 and 1. Therefore, the intersection between the two lists would be 0 and 1.

Performing Python List Intersection

Now, we shall look into some methods of intersecting lists in python:

1. Using the intersection() function
2. Applying & between sets
3. Using list comprehension
4. With filter and lambda
5. Using numpy.intersect1d() function
6. Creating a user-defined function
7. Using Collections Counter

1. Using the Intersection() function

Intersection() is a pre-defined function in python used to perform intersection between two elements of a set. It returns a new set with the common values from the input sets. For this, we have to convert the list to set explicitly.

Let us take the following two lists, A and B. Then, we shall use set() to convert A and B from lists to sets. After the conversion, set(A) will call the intersection() method, where the set(B) would be passed as an argument to the function. Then, we will use list() to convert the obtained set output into a list. The intersected list will be saved into a variable named ‘intersect’.

A = [0,1,10,5,8]
B = [7,1,3,11,0]
intersect = list(set(A).intersection(set(B)))
print(intersect)

The Output is:

[0, 1]

2. Applying & between sets

Another way of performing python list intersection is by converting the lists into sets and then applying & between the two sets. This will return the common elements from both sets. We can explicitly convert both sets into lists.

Let us take the following example:

We have first applied set() on the lists A and B. Then, we apply the and operand & between the two sets. We have explicitly converted it into list type using list() and saved it into a variable named ‘intersect’ to the set output.

A = [0,1,10,5,8]
B = [7,1,3,11,0]
intersect = list(set(A) & set(B))
print(intersect)

On printing ‘intersect’, the output is:

[0, 1]

3. Using list comprehension

We can also perform list intersection using list comprehension. List comprehension provides a compact syntax for creating a new list using an already existing list.

Here, inside the statement ‘i for i in A if i in B’, we want to append element ‘i’ inside our list ‘intersect’ for every element in ‘A’, if the same element exists in ‘B’. The element will be added to the list only if it fulfills the given condition. Else, the element will be discarded.

A = [0,1,10,5,8]
B = [7,1,3,11,0]
intersect = [i for i in A if i in B]
print(intersect)

The output list ‘intersect’ is:

[0, 1]

4. Using filter and lambda

Filter in python is an inbuilt function that is used to filter out elements from a given list. We pass each element from the list to the given function. Only those elements will be included for which the function returns True value.

Lambda is an anonymous function that only contains a single line expression. We will be using both filter and lambda to perform intersection between two lists. First, inside we have a lambda function where we return the common elements. And for all the true values, the filter will only include those values in the list ‘intersect’.

A = [0,1,10,5,8]
B = [7,1,3,11,0]
intersect = list(filter(lambda x:x in A,B))
print(intersect)

The output is:

[1, 0]

5. With numpy.intersect1d() function

We can also use the intersect1d() function present in the numpy library to achieve a list intersection. We will pass two lists as arguments, and it will return the unique values from both lists in a sorted manner. The output will then be explicitly converted to a list using the list() function.

The example is :

import numpy as np
A = [0,1,10,5,8]
B = [7,1,3,11,0]
intersect = list(np.intersect1d(A, B))
print(intersect)

Output:

[0, 1]

6. Creating a user defined function

We can also build a user-defined function for performing intersection. If an element exists in list1, we will append that element in a new list ‘intersect’ if it is present in list2 too. We achieve this using for loop and if statement. The function will then print the list ‘intersect’.

The code for the function is:

def intersect(list1, list2):
  intersect = []
  for i in list1:
    if i in list2:
      intersect.append(i)
  print(intersect)


A = [0,1,10,5,8]
B = [7,1,3,11,0]

intersect(A,B)

The output is:

[0, 1]

7. Using Collections Counter

A counter is a container that keeps track of the frequency of each element in the container. We shall have to import Counter from collections. The code to do so is:

from collections import Counter
A = Counter([0,1,10,5,8])
B = Counter([7,1,3,11,0])
A &= B
intersect = list(A.elements())
print(intersect)

The output is:

[0, 1]

List intersection in multi-dimensional lists

To perform intersection for lists of dimensions more than one, we can make use of reduce() function. Reduce() is used to apply a function to an iterable and then reduce it to a single value.

For using reduce, we will import it from functools. Here, we have taken a two-dimensional list A. We shall use the intersection() function inside reduce() and convert each sub-list into a set. Then, we shall be comparing each set with another and keep only the common unique values. In the end, reduce() will keep only the common values. We shall convert it into a list using list() and print the list.

from functools import reduce
A = [[0,6,3,2],[7,0,1,6], [6,7,10,0]]

intersect = list(reduce(set.intersection, [set(x) for x in A ]))

print(intersect)

The output is:

[0, 6]

That wraps up the python list intersection. If you have any questions in mind, leave them below in the comments.

Until next time, Keep Learning!

In this tutorial, you’ll learn how to use Python to find the intersection between two lists. Intersection means finding the common elements between two lists. Typically, intersection is set-based, meaning that the values are unduplicated.

You will learn some naive methods to find intersection between two Python lists, including for loops and list comprehensions, using the set .intersection() method and using numpy.

The Quick Answer: Use Python Set Operations

Using a Python For Loop to Find Intersection Between Two Lists

Using a Python for loop is an easy, intuitive way to find the intersection between two lists. The benefit of understandability here comes at a performance hit with lists of much larger sizes.

What we’ll do, is loop over each item in a list and see if it exists in the other. If it does, then we append it to a new list. If it doesn’t, then we’ll do nothing.

Let’s take a look at what this code would look like:

# Find intesection between two Python lists using a for loop
list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['b', 'd', 'e', 'f', 'g']

intersection = list()

for item in list1:
    if item in list2:
        intersection.append(item)

print(intersection)

# Returns: ['b', 'd', 'e']

In the next section, you’ll learn how to turn this for loop into a Python list comprehension.

Want to learn more about Python for-loops? Check out my in-depth tutorial that takes your from beginner to advanced for-loops user! Want to watch a video instead? Check out my YouTube tutorial here.

Using List Comprehensions to find the Intersection Between Two Python Lists

In many cases, a Python for loop can be turned into a list comprehension. The benefit of doing this is the ease of coding it out. Python list comprehensions comes with some key benefits:

1. You don’t need to instantiate a new, empty list
2. The code generally only spans a single line, rather than multiple lines

Essentially, the algorithm we’ll follow is the same as the for loop: we loop over each item and see if it exists in the other list. If it does, then we add it to our new list.

Let’s see what this would look like in Python:

# Find intesection between two Python lists using a list comprehension
list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['b', 'd', 'e', 'f', 'g']

intersection = [item for item in list1 if item in list2]

print(intersection)

# Returns: ['b', 'd', 'e']

Similar to the for loop method, as your list sizes grow, this can encounter some performance hiccups. This is where the next method comes into play. In the next section, you’ll learn how to use Python set methods to find the intersection between two lists.

Want to learn more about Python list comprehensions? Check out this in-depth tutorial that covers off everything you need to know, with hands-on examples. More of a visual learner, check out my YouTube tutorial here.

Using Python Set Operations to find the Intersection Between Two Lists

Python sets are similar to lists, but they have a number of key differences. While lists are ordered, sets are unordered; while lists can hold duplicate items, sets cannot.

Sets also come with a number of helpful methods. In the example below, we’ll use the .intersection() method to generate a set of items that exist between both sets.

Let’s take a look at what our code looks like:

# Find intesection between two Python lists using set.intersection()
list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['b', 'd', 'e', 'f', 'g']

intersection = list(set(list1).intersection(set(list2)))

print(intersection)

# Returns: ['b', 'd', 'e']

Let’s take a look at what we’ve done:

1. We converted both lists to sets
2. We then applied the .intersection() method
3. Finally, we convert the final set back to a list

In the next section, you’ll learn how to use the & operator to find the intersection between two lists.

Want to learn how to use the Python zip() function to iterate over two lists? This tutorial teaches you exactly what the zip() function does and shows you some creative ways to use the function.

Using the And Operator to Find Python List Intersection

In the example above, you learned how to use a set method, the .intersection() method, to find the intersection between two lists. We can also use a boolean method, using the & operator, to find the intersection between two sets.

Using this operator evaluates whether items exist in both sets and returns items that meet the criteria.

Let’s take a look at what this look like:

# Find intesection between two Python lists using &
list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['b', 'd', 'e', 'f', 'g']

intersection = list(set(list1) & set(list2))

print(intersection)

# Returns: ['b', 'd', 'e']

In the next example, you’ll learn how to use numpy to check for items that exist in two lists.

Check out some other Python tutorials on datagy, including our complete guide to styling Pandas and our comprehensive overview of Pivot Tables in Pandas!

Using Numpy to Find the Intersection Between Two Lists

Numpy is a helpful library that uses a list-like object called the np.array. These arrays are similar to Python lists but allow us to work with numpy array methods. One of these methods is the intersect1d() method, which, well, allows us to find the intersection between 1 dimensional arrays.

Let’s take a look at what this code looks like:

# Find intesection between two Python lists using numpy
list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['b', 'd', 'e', 'f', 'g']

intersection = list(np.intersect1d(list1, list2))

print(intersection)

# Returns: ['b', 'd', 'e']

Let’s explore what we’ve done here:

1. We pass our two lists into the np.intersect1d() method
2. This returns an np.array that only includes the intersection between the two lists
3. Finally, we convert this array back into a list

Need to check if a key exists in a Python dictionary? Check out this tutorial, which teaches you five different ways of seeing if a key exists in a Python dictionary, including how to return a default value.

Conclusion

In this post, you learned how to use Python to find the intersection between two lists. You learned that the easiest way to do this is to use Python set operations – in particular, using the .intersection() method. You also learned some naive implementations, including using for loops and list comprehensions. These methods, while not always the fastest to write, allow you to gain a strong understanding of how these algorithms work. Finally, you learned how to use numpy to find the intersection between two lists.

To learn more about the set .intersection() method, check out the official documentation here.