> > ... "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. > -- http://mail.python.org/mailman/listinfo/python-list