[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