Python list intersection efficiency: generator or filter()?
Your solution has a complexity of O(m*n)
, where m
and n
are the respective lengths of the two lists. You can improve the complexity to O(m+n)
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 (that is, almost never), you can also use
result = filter(set(a).__contains__, b)
which is about 20 percent faster than the other solutions on my machine.
Neither of these. The best way is to use sets.
list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = set(list1).intersection(list2)
Sets are iterable, so no need to convert the result into anything.