Entry

Fast intersect, unique, ...

Jul 5th, 2000 09:59
Nathan Wallace, Hans Nowak, Snippet 61, Michael Scharf

"""
Packages: basic_datatypes.dictionaries
"""

"""
> Right on both counts.  Using a dict restricts it to sequences all of
> whose elements are hashable, though.  Under that assumption, you're
> better off with this (which does more of the work at C speed):
> 
> def intersect(s1, s2):
>     d = {}
>     for x in s1:
>         d[x] = 1
>     return filter(d.has_key, s2)

You can do even more work at C speed:
"""

import operator
def intersect1(s1, s2):
    d = {}
    map(operator.__setitem__,len(s1)*[d],s1,s1)
    return filter(d.has_key, s2)


import operator
def intersect2(s1, s2):
    d = {}
    if len(s1)> len(s2): # map creates two temporary arrays of size len(s1)
        s1,s2=s2,s1      # take the shorten one as s1...
    map(operator.__setitem__,len(s1)*[d],s1,s1)
    return filter(d.has_key, s2)