filter list fast

[Ben Cartwright]

lars_woetmann wrote:
> I have a list I filter using another list and I would like this to be
> as fast as possible
> right now I do like this:
>
> [x for x in list1 if x not in list2]
>
> i tried using the method filter:
>
> filter(lambda x: x not in list2, list1)
>
> but it didn't make much difference, because of lambda I guess
> is there any way I can speed this up

Both of these techniques are O(n^2).  You can reduce it to O(n log n)
by using sets:

>>> set2 = set(list2)
>>> [x for x in list1 if x not in set2]

Checking to see if an item is in a set is much more efficient than a
list.

--Ben