Re: mutable objects as dictionary keys

[Erik Jones]

On Oct 9, 2007, at 12:44 PM, Andreas Kraemer wrote:

> Hi everyone,
>
> I know that the subject of mutable objects as dictionary keys has  
> been discussed a number of times in this forum (see for instance  
> "freezing" of classes), but I would love to hear the thoughts of  
> the experts on the approach below.
>
> The use case that I encounter frequently is the classification of  
> objects according to certain rules or properties: Say, I have  
> objects A, B, C, ... (e.g. instances of a class, dict, etc), I can  
> write
>
> d = {}
> d.setdefault(A,[]).append(A)
> d.setdefault(B,[]).append(B)
> ...
>
> so objects that map to the same hash key will end up in the same  
> bucket. (A "real world" example I had to deal with recently was for  
> instance the construction of a directed acyclic graph from many  
> directed trees where identical subtrees needed to be identified.)
>
> The easiest way is of course to define custom __hash__() and __eq__ 
> () methods, but this breaks if objects are mutated (accidentally)  
> after having been inserted into the dictionary. The "best" working  
> approach I came up with so far is to generate an "immutable view" V  
> of a mutable object O according to my classification rule, delegate  
> O.__hash__ and O.__eq__ to V, and make sure that the V is memoized  
> and cannot (easily) be altered later, even when O is mutated:
>
> def hashable_mutable_factory(mutable,rule):
>   class _mutable(mutable):
> def __init__(self,*args,**kw):
>   self._view_cache = {}
>   super(_mutable,self).__init__(*args,**kw)
> def _view(self):
>   id_ = id(self)
>   if not self._view_cache.has_key(id_):
> self._view_cache[id_] = rule(self)
>   return self._view_cache[id_]
> def __hash__(self):
>   return hash(self._view())
> def __eq__(self,other):
>   return self._view() == other._view()
>   return _mutable
>
> E.g.:
>
> >>> hashable_dict = hashable_mutable_factory(dict,lambda obj:  
> frozenset(obj.iteritems()))
> >>> h = hashable_dict(a=1,b=2)
> >>> d = {}
> >>> d[h] = 'foo'
> >>> d
> {{'a': 1, 'b': 2}: 'foo'}
> >>> h['c'] = 'bar'
> >>> d
> {{'a': 1, 'c': 'bar', 'b': 2}: 'foo'}
> >>> g = hashable_dict(a=1,b=2)
> >>> h
> {'a': 1, 'c': 'bar', 'b': 2}
> >>> g
> {'a': 1, 'b': 2}
> >>> id(g) == id(h)
> False
> >>> g == h
> True
>
> I slightly favor the factory function idiom above over defining the  
> rule in a super class (this would have to be done for each mutable  
> type and rule function separately), especially since I read that  
> future versions of python (2.6 ?, 3.0 ?) will contain class  
> decorators and allow syntax like class A(*bases): pass
>
> Is there a better approach? Any comments are appreciated.
>
> I have been seriously using Python for one year know, mostly in the  
> context of graph algorithms etc., and it has always been a  
> delightful coding experience!

I can definitely see how this would be useful for the real world  
example you mentioned for pruning trees and what-not.

Erik Jones

Software Developer | Emma®
[EMAIL PROTECTED]
800.595.4401 or 615.292.5888
615.292.0777 (fax)

Emma helps organizations everywhere communicate & market in style.
Visit us online at http://www.myemma.com


-- 
http://mail.python.org/mailman/listinfo/python-list

mutable objects as dictionary keys

[Andreas Kraemer]

Hi everyone,

I know that the subject of mutable objects as dictionary keys has been 
discussed a number of times in this forum (see for instance "freezing" of 
classes), but I would love to hear the thoughts of the experts on the approach 
below. 

The use case that I encounter frequently is the classification of objects 
according to certain rules or properties: Say, I have objects A, B, C, ... 
(e.g. instances of a class, dict, etc), I can write

d = {}
d.setdefault(A,[]).append(A)
d.setdefault(B,[]).append(B)
...

so objects that map to the same hash key will end up in the same bucket. (A 
"real world" example I had to deal with recently was for instance the 
construction of a directed acyclic graph from many directed trees where 
identical subtrees needed to be identified.)

The easiest way is of course to define custom __hash__() and __eq__() methods, 
but this breaks if objects are mutated (accidentally) after having been 
inserted into the dictionary. The "best" working approach I came up with so far 
is to generate an "immutable view" V of a mutable object O according to my 
classification rule, delegate O.__hash__ and O.__eq__ to V, and make sure that 
the V is memoized and cannot (easily) be altered later, even when O is mutated:

def hashable_mutable_factory(mutable,rule):
  class _mutable(mutable):
def __init__(self,*args,**kw):
  self._view_cache = {}
  super(_mutable,self).__init__(*args,**kw)
def _view(self):
  id_ = id(self)
  if not self._view_cache.has_key(id_):
self._view_cache[id_] = rule(self)
  return self._view_cache[id_]
def __hash__(self):
  return hash(self._view())
def __eq__(self,other):
  return self._view() == other._view()
  return _mutable

E.g.:

>>> hashable_dict = hashable_mutable_factory(dict,lambda obj: 
>>> frozenset(obj.iteritems()))
>>> h = hashable_dict(a=1,b=2)
>>> d = {}
>>> d[h] = 'foo'
>>> d
{{'a': 1, 'b': 2}: 'foo'}
>>> h['c'] = 'bar'
>>> d
{{'a': 1, 'c': 'bar', 'b': 2}: 'foo'}
>>> g = hashable_dict(a=1,b=2)
>>> h

{'a': 1, 'c': 'bar', 'b': 2}

>>> g

{'a': 1, 'b': 2}
>>> id(g) == id(h)
False
>>> g == h
True

I slightly favor the factory function idiom above over defining the rule in a 
super class (this would have to be done for each mutable type and rule function 
separately), especially since I read that future versions of python (2.6 ?, 3.0 
?) will contain class decorators and allow syntax like class A(*bases): pass

Is there a better approach? Any comments are appreciated. 

I have been seriously using Python for one year know, mostly in the context of 
graph algorithms etc., and it has always been a delightful coding experience!

Best regards,

Andreas




-- 
http://mail.python.org/mailman/listinfo/python-list