[Tutor] Simple way to compare Two lists

jim stockford jim at well.com
Fri Aug 17 05:01:43 CEST 2007


Why is a dict lookup constant time. I.e. if there's a
loop that walks a (shorter) list and compares each
element with each element of a dict, what's going
on to make this faster than an outer loop walking
a list and an inner loop walking a second list?



On Aug 16, 2007, at 5:01 PM, Stephen McInerney wrote:

>
> 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
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor



More information about the Tutor mailing list