CODEWITHSUNDEEP
pythonpython-3.xlistdictionarylist-comprehension
Kallol
Kallol

Reputation: 2189

fastest way find the common elements of two lists without changing the sequence of first list

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 ?

Upvotes: 2

Views: 1291

Answers (3)

nakamume
nakamume

Reputation: 800

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)]

Upvotes: 0

SIREN
SIREN

Reputation: 181

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}]

Upvotes: -1

Selcuk
Selcuk

Reputation: 59219

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]

Upvotes: 5

Related Questions