[Tutor] newB Q: extracting common elements from 2 lists

[Alexandre Ratti]

At 18:41 24/06/2002 -0400, you wrote:
>Date: Mon, 24 Jun 2002 10:35:33 -0700
>From: "Jeff Shannon" <jeff@ccvcorp.com>
>Subject: Re: [Tutor] newB Q: extracting common elements from 2 lists

[Extracting common items from two lists]
>An alternate way of doing this, that does *not* suffer from that
>logarithmic slowdown, is to take advantage of the properties of Python
>dictionaries -- a dictionary lookup takes constant time, no matter how
>many elements are in the dictionary.  So, first we can convert list a
>into a dictionary --

>(We're only worried about the existence of items, so we can just use 1
>as the value for each element in the dictionary.)  Now, we go through
>list b, and each item that's in list b *and* the dictionary gets added
>to list ab --
>
> >>> ab = []
> >>> for item in b:
>...     if tempdict.haskey(item):
>...         ab.append(item)
>...
> >>>

I remember dictionaries support "in" in Python 2.2. We could also write:

 >>> a = {1:0, 2:0, 3:0, 4:0}
 >>> b = {3:0, 4:0, 5:0}
 >>> print  [x for x in a if x in b]
[3, 4]

or

 >>> a = [1, 2, 3, 4]
 >>> b = {3:0, 4:0, 5:0}
 >>> print  [x for x in a if x in b]
[3, 4]

Do we get the same speedup?

Is it useful to store the "a" values in a dictionary here, or is the 2nd 
form the optimal one? I guess we need to iterate over the values of a, 
hence a sequence is probably the best fit?


Cheers.

Alexandre