[Tutor] Faster list searching?

Kent Johnson kent37 at tds.net
Wed Nov 18 23:59:56 CET 2009


On Wed, Nov 18, 2009 at 4:51 PM, GoodPotatoes <goodpotatoes at yahoo.com> wrote:
> I'm dealing with bigger lists than I have been, and noticed this is getting
> really slow.  Is there a faster way to do this?
>
> for x in list1:
>     if x not in list2:
>         list3.append(x)
>
> My search is taking up to 5 minutes to complete.

If you can, use a set instead of list2. "x not in list2" does a linear
search of list2 for x, which takes time proportional to the length of
list2. Searching a set takes constant time - it doesn't depend on the
size of the set. Also you can use a list comprehension to speed up the
outer loop a little:

set_of_list2 = set(list2)
list3 = [ x for x in list1 if x not in set_of_list2 ]

Note this will only work if the elements of list2 are hashable
(useable as dict keys).

Kent


More information about the Tutor mailing list