2

I have two lists,

 l1 = [1,4,3,2,5]
 l2 = [4,3,2,10]

Now I want to find the common element between to lists so I am using following code,

list(set(l1).intersection(set(l2)))
>> [2, 3, 4]

But its changing the sequence of the l1, I don't want to change the sequence so the result should be ,

>> [4, 3, 2]

Looking for the fastest way to do this without changing the sequence ?

Selcuk
  • 57,004
  • 12
  • 102
  • 110
Kallol
  • 2,089
  • 3
  • 18
  • 33
  • Does this answer your question? [Python maintain order in intersection of lists](https://stackoverflow.com/questions/29755585/python-maintain-order-in-intersection-of-lists) – iGian Apr 22 '21 at 06:46

3 Answers3

5

You can re-sort the result using l1:

>>> sorted(set(l1).intersection(set(l2)), key=l1.index)
[4, 3, 2]

You could have also used a list comprehension instead of a set intersection but I believe the first method would be generally faster depending on the number of elements in each list, because searching a list is O(n) and the solution below becomes O(n*m):

>>> [i for i in l1 if i in l2]
[4, 3, 2]

Finally, you can optimise the comprehension method by converting l2 to a set:

>>> s2 = set(l2)
>>> [i for i in l1 if i in s2]
[4, 3, 2]
Selcuk
  • 57,004
  • 12
  • 102
  • 110
  • Just adding some analysis- converting l2 to a set and checking l1 against it is the efficient solution, and should be used. It also maintains multiple copies of the same value if they appear in l1, maintains order, and does the minimum amount of work. The other solutions presented here are significantly slower for larger inputs. – Arthur.V Apr 22 '21 at 06:39
0

Let's say you want to preserve l1's sequence. An algorithm of O(n^2) time complexity would be to find for every item x in l1 if x exists in l2. Following code would work

common_elements = [x for x in l1 if x in l2]

You can reduce time complexity to O(n) by using a map(dict)

lookup_map = {x: True for x in l2}
common_elements = [x for x in l1 if x in lookup_map]

Edit: Found out that Python's set is implemented as a hash-map and lookups take O(1) in average case https://wiki.python.org/moin/TimeComplexity, so following should also have an avg. case complexity of O(n)

common_elements = [x for x in l1 if x in set(l2)]
nakamume
  • 660
  • 6
  • 11
-1

The fastest way depends on data, but this solution should be one of the fastest

[x for x in [1, 4, 3, 2, 5] if x in {4, 3, 2, 10}]
SIREN
  • 161
  • 1
  • 5