Intersection of two lists, keeping duplicates in the first list

Question

I have two flat lists where one of them contains duplicate values. For example,

array1 = [1,4,4,7,10,10,10,15,16,17,18,20]
array2 = [4,6,7,8,9,10]

I need to find values in array1 that are also in array2, KEEPING THE DUPLICATES in array1. Desired outcome will be

result = [4,4,7,10,10,10]

I want to avoid loops as actual arrays will contain over millions of values. I have tried various set and intersect combinations, but just couldn't keep the duplicates..

you can't avoid loops.. if you use library functions.. they actually use loops in their design — mlwn, Oct 30 '14 at 21:12

anon582847382 · Accepted Answer · 2014-10-30T21:19:41.417

8

What do you mean you don't want to use loops? You're going to have to iterate over it one way or another. Just take in each item individually and check if it's in array2 as you go:

items = set(array2)
found = [i for i in array1 if i in items]

Furthermore, depending on how you are going to use the result, consider having a generator:

found = (i for i in array1 if i in array2)

so that you won't have to have the whole thing in memory all at once.

edited Oct 30 '14 at 21:19

answered Oct 30 '14 at 21:12

anon582847382

19,907
5
54
57

I mean I want to know if there is an efficient way to do this as I will be working with very large size arrays with timing restrictions.. – user32147 Oct 30 '14 at 21:16
@user32147: Why don't you specify the sizes of the arrays (more precisely than "over millions of values") and the timing restrictions? – NPE Oct 30 '14 at 21:17
@user32147 This is pretty efficient: You're not gonna get any faster than O(n). But see my edit anyway, I've made a small improvement to the answer. – anon582847382 Oct 30 '14 at 21:18
1

you can use `set(array2)` – Padraic Cunningham Oct 30 '14 at 21:20
@PadraicCunningham Already mentioned that in the answer, but I'll make the point a bit better. – anon582847382 Oct 30 '14 at 21:20

score 5 · Answer 2 · answered Oct 30 '14 at 21:13

There following will do it:

array1 = [1,4,4,7,10,10,10,15,16,17,18,20]
array2 = [4,6,7,8,9,10]
set2 = set(array2)
print [el for el in array1 if el in set2]

It keeps the order and repetitions of elements in array1.

It turns array2 into a set for faster lookups. Note that this is only beneficial if array2 is sufficiently large; if array2 is small, it may be more performant to keep it as a list.

score 0 · Answer 3 · answered Aug 15 '19 at 12:59

0

Following on from @Alex's answer, if you also want to extract the indices for each token, then here's how:

found = [[index,i] for index,i in enumerate(array1) if i in array2]

answered Aug 15 '19 at 12:59

Patrick Stacey

77
9

Intersection of two lists, keeping duplicates in the first list

3 Answers3

Linked

Related