Is there such an idiom?

[Michael Spencer]

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