[Tutor] Simple way to compare Two lists

[Stephen McInerney]

Sorting both lists is unnecessary and not very scalable (order(NlogN)).

Assuming the lists do not contain duplicates,
just turn the longer one into a dict and check that each element of the
shorter list in that dict (e.g. "if j not in BigList: return false")
Since dict lookup is constant-time O(1), this approach is O(M)
i.e. speed is linear in the length of the shorter list;
and memory requirement is O(N+M) i.e. linear in the length
of the longer list. If M<<N this really saves you time.

Stephen


>From: Jaggo <jaggojaggo at yahoo.com>
>Reply-To: jaggojaggo at yahoo.com
>To: tutor at python.org
>Subject: Re: [Tutor] Simple way to compare Two lists
>Date: Thu, 16 Aug 2007 10:11:14 -0700 (PDT)
>
>Thank you Kent, Michael, Tom and anyone else I'm forgetting who took time 
>to reply.
>
>I don't work quite so fast, very limited personal computer time means I 
>only do it on weekends,
>
>I read through your suggestions and eventually found a way to speed-up the 
>proccess through sorting the Two lists, then manually iterating through 
>each of them. This way I've completely canceled the need to compare Two 
>lists: instead just ensuring I start from a point not taken in One list and 
>having to only check whether Item not in BigList.
>
>[If anyone's interested, I should have the script finished and thoroughly 
>tested on, ah, next weekend, and I could post a link here.]
>
>Again, Thx.
>-Omer.
>
>Message: 1
>Date: Fri, 10 Aug 2007 08:11:47 -0400
>From: Kent Johnson
>Subject: Re: [Tutor] Simple way to compare Two lists
>To: Tom Fitzhenry , tutor at python.org
>Message-ID: <46BC5603.9060703 at tds.net>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>Tom Fitzhenry wrote:
> > On Fri, Aug 10, 2007 at 02:54:44AM -0700, Jaggo wrote:
> >> Can anyone think of any better way?
> >
> > If SmallList and BigList are sorted (in order), there is a faster 
>method:
> >
> > def IsAPartOfList(SmallList,BigList):
> >     for i in BigList:
> >         for j in SmallList:
> >             if i==j:
> >                 return true
> >             if i>j:
> >                 break
> >     return false
> >
> > (I'm not sure how encouraged using break statements are, so wait for a 
>tutor to
> > answer)
>
>break is fine! If the list you are searching is sorted you can use the
>bisect module to do a binary search instead of the linear search above.
>
> > If one list is already sorted but the other isn't, it may still be 
>faster to
> > sort the unsorted list then use the method above.
>
>I don't think BigList has to be sorted in the above algorithm. If both
>lists are sorted I suppose you could write it like a merge sort, walking
>along both lists looking for a match.
>
>Kent
>
>
>
>
>---------------------------------
>Park yourself in front of a world of choices in alternative vehicles.
>Visit the Yahoo! Auto Green Center.


>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor

_________________________________________________________________
See what you’re getting into…before you go there 
http://newlivehotmail.com/?ocid=TXT_TAGHM_migration_HM_viral_preview_0507