On Dec 24, 12:52 pm, Carl Banks <pavlovevide...@gmail.com> wrote: > On Dec 24, 1:16 pm, 5lvqbw...@sneakemail.com wrote: > > > > > > > Hi, > > > 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. > > I'm not sure how large each set will be, but the point is I'm trying > > to avoid anything looking like an O(n^2) algorithm, so I can't just > > use naive double-looping to check for intersection/union on a pair of > > lists. > > > The only way I can think of to do this right is to hash the dicts by > > freezing them, turning them all into tuples, which can then be > > hashed. But this is a problem because more dicts might be nested > > inside. At any rate, I'd need to thaw them out when I'm done and turn > > them back into dicts, which seems complicated and annoying, and all > > this leads me to believe there is a better way. > > > 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? > > > How do you get the object back from an ID in python? > > Quick and dirty way is to reference the dicts with a lightweight > hashable object that uses the dict's identity. For instance: > > class Identity(object): > def __init__(self,obj): > self.obj = obj > def __hash__(self): > return hash(id(self.obj)) > def __eq__(self,other): > return self.obj is other.obj > > Then, instead of "s.add(d)" use "s.add(Identity(d))". > > Instead of "d = s.pop()" use "d = s.pop().obj". > > Instead of "d in s" use "Identity(d) in s". > > And so on. > > To do it a bit better, you could create an IdentitySet class that > subclasses set and wraps the methods so that they automatically apply > wrap and unwrap the arguments on their way in and out (I'd bet there's > already a cookbook recipe to do that). > > Carl Banks
Thank you, I like this idea a lot. It's close to what I've been thinking but a bit cleaner. Michael -- http://mail.python.org/mailman/listinfo/python-list