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 <[EMAIL PROTECTED]> >> Reply-To: [EMAIL PROTECTED] >> To: tutor@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@python.org >> Message-ID: <[EMAIL PROTECTED]> >> 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@python.org >> http://mail.python.org/mailman/listinfo/tutor > > _________________________________________________________________ > See what youre getting into > before you go there > http://newlivehotmail.com/? > ocid=TXT_TAGHM_migration_HM_viral_preview_0507 > > _______________________________________________ > Tutor maillist - Tutor@python.org > http://mail.python.org/mailman/listinfo/tutor _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
