Geek Answers Handbook

Python list crossing efficiency: generator or filter ()?

I would like to cross two lists in Python (2.7). I need the result to be iterable:

list1 = [1,2,3,4] list2 = [3,4,5,6] result = (3,4) # any kind of iterable

Ensuring a full iteration will be performed primarily after crossing, which of the following functions is more efficient?

Using a generator:

 result = (x for x in list1 if x in list2)

Using filter ():

 result = filter(lambda x: x in list2, list1)

Other offers?

Thanks in advance,
Amnon

+4
source share
3 answers

None of them. The best way is to use kits.

 list1 = [1,2,3,4] list2 = [3,4,5,6] result = set(list1).intersection(list2)

Sets are repeatable, so there is no need to convert the result to anything.

+14
source

Your solution has complexity O(m*n) , where m and n are the corresponding lengths of two lists. You can improve O(m+n) complexity by using a set for one of the lists:

 s = set(list1) result = [x for x in list2 if x in s]

In cases where speed matters more than readability (i.e. almost never), you can also use

 result = filter(set(a).__contains__, b)

which is about 20% faster than other solutions on my machine.

+7
source

for a list of lists, the most efficient way is to use:

 result = set(list1).intersection(list2)

as mentioned, but for numpy arrays the intersection1d function is more efficient:

 import numpy as np result = np.intersection1d(list1, list2)

In particular, when you know that lists have no duplicate values, you can use it like:

 result = np.intersection1d(list1, list2, assume_unique=True)
0
source

More articles:


All Articles