finding item in two lists efficiently Python

Question

I have a working function to allow me to search two lists and see if the items in list1 are present in list2, if an item is not present in list2 from list1 then I would like that output to another list. However this takes AGES to run and I was wondering if there is a faster way to do this.

def compare(list1,list2):
    x=[]
    for i in list1:
        if i not in list2:
            x.append(i)

    return x

Answer 1

Since you're only checking for inclusion in list2, make that one a set:

def compare(list1, list2):
    s2 = set(list2)
    result = [i  for i in list1  if i not in s2] # simple list comprehension
    return result

This preserves the input order and semantics of your program, while being significantly faster: set inclusion testing is O(1), while list inclusion testing is O(n), bringing your whole algorithm from O(n^2) down to O(n).