Doing set operation on non-hashable objects

[5lvqbwl02 at sneakemail.com]

> > ... "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.
>
> Well, if the lists are ordered, you can do intersection and union
> in O(n) time.  If they are orderable, you can sort each first, giving
> O(n log n).  Note you can do lst.sort(key=id) which will sort on ids.

The lists are not ordered, since the elements of the list could be
arbitrarily complex things consisting of resistors, capacitors, sub-
circuits, etc.  I'm trying do a little EDA program, taking the best
parts from the different EDA/cad tools I've used.  I finally came up
with an idea using dictionaries in a certain way, so I'd like to be
able to do set operators on arbitrary things that may themselves not
be hashable.

> > How do you get the object back from an ID in python?
>
> You don't; you remember the mapping in a dictionary and look it up.

Exactly.  A mapping between the ID and the thing itself.

> If there were a way to go from id to object, the whole idea of garbage
> collection and reference counts would fly out the window, leading to
> nasty crashes (or you might get to an object that is the re-used id of
> an older object).

Yup, this makes perfect sense.  It was rattling around in my head for
a bit afer I wrote the original post, then this makes sense.

>