1

I have written the following code to find elements in a list that are also within another list. However This algorithm is n squared in Big O, is there a better way of getting around this? thanks in advance

def printCommon(list1,list2):
    for i in list1:
        found = False
        for j in list2:
            if i == j:
                print i
                break
if __name__ == "__main__":
    list1 = [1,2,3,4,5]
    list2 = [9,8,7,6,5]
    printCommon(list1,list2)
godzilla
  • 3,005
  • 7
  • 44
  • 60

1 Answers1

1

As a more efficient way you can use set.intersection :

>>> set(list1).intersection(list2)
set([5])

A bench mark:

from timeit import timeit

s1="""
def printCommon(list1,list2):
    for i in list1:
        found = False
        for j in list2:
            if i == j:
                #print i
                break

list1 = [1,2,3,4,5]
list2 = [9,8,7,6,5]
printCommon(list1,list2)
"""
s2="""
list1 = [1,2,3,4,5]
list2 = [9,8,7,6,5]
set(list1).intersection(set(list2))
    """

result :

first:  0.129281997681
second :  0.0606861114502
Mazdak
  • 105,000
  • 18
  • 159
  • 188
  • but does this do something similar underneath? – godzilla Mar 19 '15 at 20:00
  • @godzilla its exactly what you want! the intersection between your lists! – Mazdak Mar 19 '15 at 20:01
  • 1
    No, it does something pretty different using hashes, making it roughly O(2n) (note to @Kasra it's not necessary to explicitly convert `list2` to a `set` for this to work) – Iguananaut Mar 19 '15 at 20:01
  • @Kasra, because he is correct, the whole idea of using set.intersection is you don't have to call set, you are adding overhead. The benchmarking has nothing to do with what Iguananaut is trying to say. – Padraic Cunningham Mar 19 '15 at 20:17
  • 1
    @PadraicCunningham yeah, im sorry i had a miss understanding about `set` and `intersection` at all (would you remember :) )!! i read the wiki and now i correct it! ;) – Mazdak Mar 19 '15 at 20:27