Doing set operation on non-hashable objects

[Scott David Daniels]

5lvqbwl02 at sneakemail.com wrote:
> ... "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.

> 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?

You don't; you remember the mapping in a dictionary and look it up.
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).

--Scott David Daniels
Scott.Daniels at Acm.Org