5lvqbw...@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.dani...@acm.org -- http://mail.python.org/mailman/listinfo/python-list
