Doing set operation on non-hashable objects

Gabriel Genellina gagsl-py2 at
Wed Dec 24 21:21:12 CET 2008

En Wed, 24 Dec 2008 17:16:59 -0200, <5lvqbwl02 at> escribió:

> I'm writing an application which is structured roughly as follows:
> "db" is a dict, where the values are also dicts.
> A function searches through db and returns a list of values, each of
> which is a dict as described above.
> I need to perform set operations on these lists (intersection and
> union)
> However the objects themselves are not hashable, and therefore can't
> be in a set, because they are dicts.

See this thread from last week:

> What I really need is a set of pointers, so at the end of the
> operation I have the actual objects pointed to.  Can I somehow use the
> object IDs as set elements, then recreate a list with the actual
> objects they point to?

If you *only* care about object identity, you might use a dictionary that  
only compares by identity to anyone else:

class nc_dict(dict):
   "A hashable dictionary that isn't equal to anyone else"

   def __eq__(self, other):
     return cmp(id(self),id(other))==0

   def __hash__(self):
     return hash(id(self))

d1 = nc_dict(a=1, b=2, c=3)
d2 = nc_dict(b=2, c=0, d=4)
d3 = nc_dict(a=1, c=3, e=5)
dd1 = nc_dict(x=d1, y=d2)
dd2 = nc_dict(x=d1, y=d3)
dd3 = nc_dict(y=d2, z=d3, w=d1)
l1 = [dd1, dd2]
l2 = [dd2, dd3]
s1 = set(l1)
s2 = set(l2)
print s1-s2
print s2-s1
print s1&s2

# instances of nc_dict with the same contents are NOT equal
d4 = nc_dict(a=1, b=2, c=3)
print d1, d4, d1==d4  # output: False

# but we can use this function to compare contents
def cmp_contents(d1, d2):
     try: return cmp(sorted(d1.items()), sorted(d2.items()))
     except Exception: return 1 # assume they're unequal

print cmp_contents(d1,d4)==0 # output: True

> How do you get the object back from an ID in python?

You don't :)

Gabriel Genellina

More information about the Python-list mailing list