Per wrote:
> Thanks Ron,
> surely set is the simplest way to understand the question, to see
> whether there is a non-empty intersection. But I did the following
> thing in a silly way, still not sure whether it is going to be linear
> time.
> def foo():
> l = [...]
> s = [...]
> dic = {}
> for i in l:
> dic[i] = 0
> k=0
> while k <len(s):
> if s[k] in dic:
> return True
> else: pass
> k+=1
> if k == len(s):
> return False
>
>
> I am still a rookie, and partly just migrated from Haskell...
> I am not clear about how making one of the lists a dictionary is
> helpful
>
The dict-based approach is to do something like this:
>>> ls1 = [1,3,5,7,9]
>>> ls2 = [3,5,6,7,10]
>>> d1 = dict.fromkeys(ls1)
>>> d1
{1: None, 3: None, 9: None, 5: None, 7: None}
Note the values, are irrelevant - we care only about the keys
Now, membership testing takes linear time:
>>> [item for item in ls2 if item in d1]
[3, 5, 7]
>>>
But, as you say, this approach is unnecessary, given sets.
HTH
Michael
--
http://mail.python.org/mailman/listinfo/python-list
