CODEWITHSUNDEEP
pythonperformance
Sam Hammamy
Sam Hammamy

Reputation: 11017

Optimal and efficient way to examine python lists

I was asked this on an interview this past week, and I didn't have the answer (the correct answer anyways). Say for instance you have list A which has the following elements [1,3,5,7,9,10] and then you have list B, which has the following elements: [3,4,5,6,7], and you want to know which elements in list B are in list A. My answer was:

for item in listA:
    for item1 in listB:
        if item1 == item:
            put item1 in some third list

But I know this is bad, because say listA is one million elements, and listB is a hundred thousand, this solution is just rubbish.

What's the best way to achieve something like this without iteration of both lists?

Upvotes: 0

Views: 293

Answers (5)

Levon
Levon

Reputation: 143082

Using list comprehension and using the in operator to test for membership:

[i for i in lista if i in listb]

would yield:

[3, 5, 7]

Alternatively, one could use set operations and see what the intersection of both lists (converted to sets) would be.

Upvotes: 1

Yuushi
Yuushi

Reputation: 26050

I'd suggest converting them both to sets and doing an intersection:

setA = set(listA)
setB = set(listB)
setA.intersection(setB)

Edit: Note that this will remove any duplicate elements that were in both lists. So if we had listA = [1,1,2,2,3] and listB = [1,1,2,3] then the intersection will only be set([1,2,3]). Also, for a worst-case estimate, this will be as slow as the list comprehension - O(n * m), where n and m are the respective lengths of the lists. Average case is a far better O(n) + O(m) + O(min(m,n)) == O(max(m,n)), however.

Upvotes: 2

Joran Beasley
Joran Beasley

Reputation: 114018

well i may as well throw filter in the mix

filter(lambda x: x in listb,lista)

Upvotes: 1

Blender
Blender

Reputation: 298344

You can use sets (preferred):

listC = list(set(listA) & set(listB))

Or a list comprehension:

listC = [i for i in listA if i in listB]

Upvotes: 0

BrenBarn
BrenBarn

Reputation: 251428

set(listA) & set(listB) is simplest.

Upvotes: 6

Related Questions