28

I want to know which elements of list_1 are in list_2. I need the output as an ordered list of booleans. But I want to avoid for loops, because both lists have over 2 million elements.

This is what I have and it works, but it's too slow:

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

booleans = []
for i in list_1:
   booleans.append(i in list_2)

# booleans = [False, False, True, True, False, False]

I could split the list and use multithreading, but I would prefer a simpler solution if possible. I know some functions like sum() use vector operations. I am looking for something similar.

How can I make my code more efficient?

New contributor
herdek550 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
4

7 Answers 7

53

I thought it would be useful to actually time some of the solutions presented here on a larger sample input. For this input and on my machine, I find Cardstdani's approach to be the fastest, followed by the numpy isin() approach.

Setup 1

import random

list_1 = [random.randint(1, 10_000) for i in range(100_000)]
list_2 = [random.randint(1, 10_000) for i in range(100_000)]

Setup 2

list_1 = [random.randint(1, 10_000) for i in range(100_000)]
list_2 = [random.randint(10_001, 20_000) for i in range(100_000)]

Timings - ordered from fastest to slowest (setup 1).

Cardstdani - approach 1


I recommend converting Cardstdani's approach into a list comprehension (see this question for why list comprehensions are faster)

s = set(list_2)
booleans = [i in s for i in list_1]

# setup 1
6.01 ms ± 15.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.19 ms ± 27.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

No list comprehension

s = set(list_2)
booleans = []
for i in list_1:
   booleans.append(i in s)

# setup 1
7.28 ms ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
5.87 ms ± 8.19 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Cardstdani - approach 2 (with an assist from Timus)


common = set(list_1) & set(list_2)
booleans = [item in common for item in list_1]

# setup 1
8.3 ms ± 34.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
6.01 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Using the set intersection method

common = set(list_1).intersection(list_2)
booleans = [item in common for item in list_1]

# setup 1
10.1 ms ± 29.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.82 ms ± 19.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

numpy approach (crissal)


a1 = np.array(list_1)
a2 = np.array(list_2)

a = np.isin(a1, a2)

# setup 1
18.6 ms ± 74.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
18.2 ms ± 47.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2 (assuming list_1, list_2 already numpy arrays)
10.3 ms ± 73.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

list comprehension


l = [i in list_2 for i in list_1]

# setup 1
4.85 s ± 14.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.6 s ± 823 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Sharim - approach 1


booleans = list(map(lambda e: e in list_2, list_1))

# setup 1
4.88 s ± 24.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48 s ± 389 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Using the __contains__ method

booleans = list(map(list_2.__contains__, list_1))

# setup 1
4.87 s ± 5.96 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.2 s ± 486 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Sharim - approach 2


set_2 = set(list_2)
booleans = list(map(lambda e: set_2 != set_2 - {e}, list_1))

# setup 1
5.46 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
11.1 s ± 75.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Varying the length of the input


Employing the following setup

import random 

list_1 = [random.randint(1, n) for i in range(n)]
list_2 = [random.randint(1, n) for i in range(n)]

and varying n in [2 ** k for k in range(18)]:

enter image description here

Employing the following setup

import random 

list_1 = [random.randint(1, n ** 2) for i in range(n)]
list_2 = [random.randint(1, n ** 2) for i in range(n)]

and varying n in [2 ** k for k in range(18)], we obtain similar results:

enter image description here

Employing the following setup

import random 

list_1 = list(range(n))
list_2 = list(range(n, 2 * n))

and varying n in [2 ** k for k in range(18)]:

enter image description here

Employing the following setup

import random 

list_1 = [random.randint(1, n) for i in range(10 * n)]
list_2 = [random.randint(1, n) for i in range(10 * n)]

and varying n in [2 ** k for k in range(18)]:

enter image description here

19
  • 3
    Thanks for your effort in timing those possibilities.
    – Cardstdani
    Apr 24 at 17:34
  • 2
    I think @Cardstdani s approach should be modified to common = set(list_1) & set(list_2); booleans = [item in common for item in list_1].
    – Timus
    Apr 24 at 17:43
  • 2
    Our trusted benchmarker
    – crissal
    Apr 24 at 17:46
  • 3
    Interesting results, thanks. With the way you generate the lists (random.randint(1, n) for i in range(n)), there are many intersections between them, which helps the not-so-efficient solutions, since they can stop iterating and return True faster. If you used random.randint(1, n**2) for example, they would look worse. And as worst-case test, you could use N = 2_000_000; list_1 = range(N); list_2 = range(N, 2*N). The set based solution would be much faster than all others in this case. 2 days ago
  • 2
    Thanks @EricDuminil for the comments. The computer is currently working on the random.randint(1, n**2) case right now. I will also try to run the worst-case test you mentioned.
    – oda
    2 days ago
32

You can take advantage of the O(1) in operator complexity for the set() function to make your for loop more efficient, so your final algorithm would run in O(n) time, instead of O(n*n):

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

s = set(list_2)
booleans = []
for i in list_1:
   booleans.append(i in s)
print(booleans)

It is even faster as a list comprehension:

s = set(list_2)
booleans = [i in s for i in list_1]

If you only want to know the elements, you can use an intersection of sets like that, which will be an efficient solution due to the use of set() function, already optimized by other Python engineers:

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

print(set(list_1).intersection(set(list_2)))

Output:

{1, 2}

Also, to provide a list format output, you can turn your resulting set into a list with list() function:

print(list(set(list_1).intersection(set(list_2))))
17
  • Sorry I wasn't clear, I need the whole list and ordered
    – herdek550
    Apr 24 at 16:51
  • 2
    @Cardstdani I was going to include a solution using set too. I want to point out that for larger lists (just tested this) the gains from using your way are huge compared to the highest-voted solution and a basic list comprehension.
    – oda
    Apr 24 at 17:06
  • 2
    @oda I've tried common = set(list_1) & set(list_2); result = [item in common for item in list_1] and it's takes about half the time of numpy.isin here.
    – Timus
    Apr 24 at 17:32
  • 1
    That's from me! Nice one!
    – oda
    Apr 24 at 18:21
  • 2
    Also, a note: If this is an operation you need to perform frequently on long-lived lists, it might be worth caching the set and keeping it updated as the list changes. That way you would avoid the O(n) hit of converting the list to a set each time. It wouldn't change the O complexity, but it would speed up runtime. You could even write/find a datatype that provides indexing and O(1) search (a list+set for lack of a better name). 2 days ago
12

If you want to use a vector approach you can also use Numpy isin. It's not the fastest method, as demonstrated by oda's excellent post, but it's definitely an alternative to consider.

import numpy as np

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

a1 = np.array(list_1)
a2 = np.array(list_2)

np.isin(a1, a2)
# array([False, False,  True,  True, False, False])
0
4

You can use the map function. If you are not familiar with the lambda function then you can check this out.

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

booleans = list(map(lambda e:e in list_2,iter(list_1)))
print(booleans)

output

[False, False, True, True, False, False]

However, if you want the only elements which are not the same then instead of a map function you can use the filter function with the same code.

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

new_lst = list(filter(lambda e:e in list_2,iter(list_1)))# edited instead of map use filter.
print(new_lst)

output

[1, 2]

Edited

I am removing the in statement from the code because in also acts as a loop. I am checking using the timeit module.

you can use this code for the list containing True and False.

This way is fastest then above one.

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)

booleans = list(map(lambda e:set_2!=set_2-{e},iter(list_1)))
print(booleans)

output

[False, False, True, True, False, False]

This one is for the list containing the elements.

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)

booleans = list(filter(lambda e:set_2!=set_2-{e},iter(list_1))) # edited instead of map use filter
print(booleans)

output

[1,2]

As Op Never use lambda function then this is for him

list_1 = [0,0,1,2,0,0]*100000
list_2 = [1,2,3,4,5,6]*100000
set_2 = set(list_2)
def func():
    return set_2!=set_2-{e}

booleans = list(map(func,iter(list_1)))

I know my way isn't the best way to this answer this because I am never using NumPy much.

15
  • 1
    Thanks, it should technically be faster. But when I implemented it, it was still too slow for me. I used instead numpy as @crissal recommended.
    – herdek550
    Apr 24 at 17:12
  • 3
    Chill out buddy, it's not a competition, just a way to help OP and hopefully other people who will run into the same problem in the future.
    – crissal
    Apr 24 at 17:38
  • 1
    True, oda's answer shows it clearly
    – crissal
    Apr 24 at 17:45
  • 1
    @herdek550 instead of lambda you can use the simple function I am editing my answer. Apr 24 at 18:41
  • 2
    I would argue differently. If we are talking about time complexities, then a constant addition to the timing (importing a library) should not be included. You can of course make a note that the numpy version takes a little longer to start up (due to the import) but in the case of large N this is not relevant. 2 days ago
3

It's probably simpler to just use the built-in set intersection method, but if you have lots of lists that you're comparing, it might be faster to sort the lists. Sorting the list is n ln n, but once you have them sorted, you can compare them in linear time by checking whether the elements match, and if they don't, advance to the next item in the list whose current element is smaller.

1

Use set() to get a list of unique items in each list

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

booleans = []

set_1 = set(list_1)
set_2 = set(list_2)

if(set_1 & set_2):
  print(set_1 & set_2)
else:
  print("No common elements")

Output:

{1, 2}
6
  • 2
    Does if(set_1 & set_2): print(set_1 & set_2) evaluate set_1 & set_2 twice, or is it smart enough to cache the result from the firth time? 2 days ago
  • @Acccumulation you would need to set it to a variable before hand then evaluate so: foo = set_1 & set_2 then if(foo): and print(foo)
    – SPYBUG96
    2 days ago
  • 2
    you can write it in one line: print((set_1 & set_2) or "No common elements"). Considering readability, I would not recommend this though
    – Aemyl
    2 days ago
  • Interesting answer to the title question, although not the list of bools this specific question was looking for. I expect building a set out of the 2nd list is similar cost to checking each element for membership in another set, and then the actual intersection is fast if the sets are small (e.g. if a large array had many duplicates). So more total work but perhaps less memory touched (than bool list) if the sets are small. Does it give any guarantees about preserving order, in case anyone needs that? Like elements of the intersection appearing in the order they did in list_1 or list_2? 19 hours ago
  • 1
    I'd recommend just leaving it in this state (maybe with a note acknowledging that it's answering a variation on the problem which people who get here from the question title might well have); existing answers already use set(list) for one of the inputs and check the other against it. Including the fastest answer in the benchmark shootout. 12 hours ago
1

If you know the values are non-negative and the maximum value is much smaller than the length of the list, then using numpy's bincount might be a good alternative for using a set.

np.bincount(list_1).astype(bool)[list_2]

If list_1 and list_2 happen to be numpy arrays, this can even be a lot faster than the set + list-comprehension solution. (In my test 263 µs vs 7.37 ms; but if they're python lists, it's slightly slower than the set solution, with 8.07 ms)

1
  • NB np.bincount has a parameter minlength that defaults to the maximum value of its input. But if list_2 contains values bigger than list_1 things will break. So to be general you'd need to set minlength=max(list_1.max(), list_2.max()) if they're numpy arrays (and you want to maintain speed) or minlength=max(max(list_1), max(list_2)) otherwise.
    – towr
    yesterday

Your Answer

herdek550 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.