Re: [Python-Dev] Getting values stored inside sets
Raymond Hettinger wrote: Hrvoje Niksic wrote: I've stumbled upon an oddity using sets. It's trivial to test if a value is in the set, but it appears to be impossible to retrieve a stored value, See: http://code.activestate.com/recipes/499299/ Thanks, this is *really* good, the kind of idea that seems perfectly obvious once pointed out by someone else. :-) I'd still prefer sets to get this functionality so they can be used to implement, say, interning, but this is good enough for me. In fact, I can derive from set and add a method similar to that in the recipe. It can be a bit simpler than yours because it only needs to support operations needed by sets (__eq__ and __hash__), not arbitrary attributes. class Set(set): def find(self, item, default=None): capt = _CaptureEq(item) if capt in self: return capt.match return default class _CaptureEq(object): __slots__ = 'obj', 'match' def __init__(self, obj): self.obj = obj def __eq__(self, other): eq = (self.obj == other) if eq: self.match = other return eq def __hash__(self): return hash(self.obj) s = Set([1, 2, 3]) s.find(2.0) 2 ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
2009/4/3 Hrvoje Niksic hrvoje.nik...@avl.com: I've stumbled upon an oddity using sets. It's trivial to test if a value is in the set, but it appears to be impossible to retrieve a stored value, other than by iterating over the whole set. Let me describe a concrete use case. Imagine a set of objects identified by some piece of information, such as a key slot (guaranteed to be constant for any particular element). The object could look like this: class Element(object): def __init__(self, key): self.key = key def __eq__(self, other): return self.key == other def __hash__(self): return hash(self.key) # ... Now imagine a set s of such objects. I can add them to the set: s = set() s.add(Element('foo')) s.add(Element('bar')) I can test membership using the keys: 'foo' in s True 'blah' in s False But I can't seem to find a way to retrieve the element corresponding to 'foo', at least not without iterating over the entire set. Is this an oversight or an intentional feature? Or am I just missing an obvious way to do this? My instinct is that it's intentional. I'd say that you're abusing __eq__ here. If you can say x in s and then can't use x as if it were the actual item inserted into s, then are they really equal? Using a dict seems like the correct answer. I certainly don't think it's worth complicating the set interface to cover this corner case. Paul. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
Hrvoje Niksic wrote: I've stumbled upon an oddity using sets. It's trivial to test if a value is in the set, but it appears to be impossible to retrieve a stored value, Set elements, by definition, do not have keys or position by which to grab. When they do, use a dict or list. other than by iterating over the whole set. Let me describe a concrete use case. Imagine a set of objects identified by some piece of information, such as a key slot (guaranteed to be constant for any particular element). The object could look like this: class Element(object): def __init__(self, key): self.key = key def __eq__(self, other): return self.key == other def __hash__(self): return hash(self.key) # ... Now imagine a set s of such objects. I can add them to the set: s = set() s.add(Element('foo')) s.add(Element('bar')) I can test membership using the keys: 'foo' in s True 'blah' in s False But I can't seem to find a way to retrieve the element corresponding to 'foo', at least not without iterating over the entire set. Is this an oversight or an intentional feature? Or am I just missing an obvious way to do this? Use a dict, like you did. I know I can work around this by changing the set of elements to a dict that maps key - element, but this feels unsatisfactory. Sorry, that is the right way. It's redundant, as the element already contains all the necessary information, Records in a database have all the information of the record, but we still put out fields for indexes. tjr ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
On Fri, 3 Apr 2009 11:22:02 pm Paul Moore wrote: I'd say that you're abusing __eq__ here. If you can say x in s and then can't use x as if it were the actual item inserted into s, then are they really equal? That's hardly unusual in Python. alist = [0, 1, 2, 3, 4] 3.0 in alist True alist[3.0] Traceback (most recent call last): File stdin, line 1, in module TypeError: list indices must be integers Besides, there's a concrete use-case for retrieving the actual object inside the set. You can ensure that you only have one instance of any object with a particular value by using a cache like this: _cache = {} def cache(obj): if obj in _cache: return _cache[obj] _cache[obj] = obj return obj Arguably, it would be neater if the cache was a set rather than a dict, thus saving one pointer per item, but of course that would rely on a change on set behaviour. -- Steven D'Aprano ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
On Sat, 4 Apr 2009 02:07:28 am Antoine Pitrou wrote: Your example is wrong: Of course it is. The perils of posting at 2am, sorry. Nevertheless, the principle still holds. There's nothing in Python that prohibits two objects from being equal, but without them being interchangeable. As poorly written as my example was, it still holds: I just need to add a level of indirection. alist = [100, 111, 102, 103, 105, 104, 106, 108] indices_of_odd_numbers = [alist.index(n) for n in alist if n%2] if Decimal('3') in indices_of_odd_numbers: ... print alist[Decimal('3')] ... Traceback (most recent call last): File stdin, line 2, in module TypeError: list indices must be integers Python does not promise that if x == y, you can use y anywhere you can use x. Nor should it. Paul's declaration of abuse of __eq__ is unfounded. -- Steven D'Aprano ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
I've stumbled upon an oddity using sets. It's trivial to test if a value is in the set, but it appears to be impossible to retrieve a stored value, other than by iterating over the whole set. Of course it is. That's why it is called a set: it's an unordered collection of objects, keyed by nothing. If you have a set of elements, and you check 'foo' in s, then you should be able just to use the string 'foo' itself for whatever you want to do with it - you have essentially created a set of strings. If you think that 'foo' and Element('foo') are different things, you should not implement __eq__ in a way that they are considered equal. Regards, Martin ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
2009/4/3 Steven D'Aprano st...@pearwood.info: Python does not promise that if x == y, you can use y anywhere you can use x. Nor should it. Paul's declaration of abuse of __eq__ is unfounded. Sorry, I was trying to simplify what I was saying, and simplified it to the point where it didn't make sense :-) Martin (quoted below) explained what I was trying to say far more clearly. 2009/4/3 Martin v. Löwis mar...@v.loewis.de: If you have a set of elements, and you check 'foo' in s, then you should be able just to use the string 'foo' itself for whatever you want to do with it - you have essentially created a set of strings. If you think that 'foo' and Element('foo') are different things, you should not implement __eq__ in a way that they are considered equal. -- in particular, if you're using things in sets (which are *all about* equality, insofar as that's how duplicates are defined) you should ensure that your definition of __eq__ respects the idea that equal objects are duplicates (ie, interchangeable). Otherwise, a dict is the appropriate data structure. Actually, given the definition in the original post, class Element(object): def __init__(self, key): self.key = key def __eq__(self, other): return self.key == other def __hash__(self): return hash(self.key) as far as I can tell, equality is *only* defined between Elements and keys - not even between 2 elements! So with that definition, there could be many Elements in a set, all equal to the same key. Which is completely insane. In fact, Python seems to be doing something I don't understand: class Element(object): ...def __init__(self, key, id): ...self.key = key ...self.id = id ...def __eq__(self, other): ...print Calling __eq__ for %s % self.id ...return self.key == other ...def __hash__(self): ...return hash(self.key) ... a = Element('k', 'a') b = Element('k', 'b') a == b Calling __eq__ for a Calling __eq__ for b True a == a Calling __eq__ for a Calling __eq__ for a True Why does __eq__ get called twice in these cases? Why does a == b, as that means a.key == b, and clearly a.key ('k') does *not* equal b. Or are there some further options being tried, in str,__eq__ or object.__eq__? The documentation doesn't say so... Specifically, there's nothing saying that a reversed version is tried. Paul. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
On Fri, 3 Apr 2009 at 17:57, Paul Moore wrote: In fact, Python seems to be doing something I don't understand: class Element(object): ...def __init__(self, key, id): ...self.key = key ...self.id = id ...def __eq__(self, other): ...print Calling __eq__ for %s % self.id ...return self.key == other ...def __hash__(self): ...return hash(self.key) ... a = Element('k', 'a') b = Element('k', 'b') a == b Calling __eq__ for a Calling __eq__ for b True a == a Calling __eq__ for a Calling __eq__ for a True Why does __eq__ get called twice in these cases? Why does a == b, as that means a.key == b, and clearly a.key ('k') does *not* equal b. Or are there some further options being tried, in str,__eq__ or object.__eq__? The documentation doesn't say so... Specifically, there's nothing saying that a reversed version is tried. a == b So, python calls a.__eq__(b) Now, that function does: a.key == b Since b is an object with an __eq__ method, python calls b.__eq__(a.key). That function does: a.key == b.key ie: the OP's code is inefficient :) --David ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
2009/4/3 R. David Murray rdmur...@bitdance.com: a == b So, python calls a.__eq__(b) Now, that function does: a.key == b Since b is an object with an __eq__ method, python calls b.__eq__(a.key). That's the bit I can't actually find documented anywhere. Ah, looking again I see that I misread the section describing the rich comparison methods: There are no swapped-argument versions of these methods (to be used when the left argument does not support the operation but the right argument does); rather, __lt__() and __gt__() are each other’s reflection, __le__() and __ge__() are each other’s reflection, and __eq__() and __ne__() are their own reflection. I read that as meaning that no reversed version was called, whereas it actually means that __eq__ is its own reversed version - and so gets called both times. Thanks for helping me clear that up! Paul. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
On Fri, Apr 3, 2009 at 8:07 AM, Hrvoje Niksic hrvoje.nik...@avl.com wrote: But I can't seem to find a way to retrieve the element corresponding to 'foo', at least not without iterating over the entire set. Is this an oversight or an intentional feature? Or am I just missing an obvious way to do this? query_obj in s True s_prime = s.copy() s_prime.discard(query_obj) x = s.difference(s_prime).pop() Pretty ugly, but I think it only uses a shallow copy, and it might be a bit better than iterating, if difference is intelligent. I haven't run any tests though. -- Cheers, Leif ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
Paul Moore wrote: 2009/4/3 R. David Murray rdmur...@bitdance.com: a == b So, python calls a.__eq__(b) Now, that function does: a.key == b Since b is an object with an __eq__ method, python calls b.__eq__(a.key). That's the bit I can't actually find documented anywhere. It doesn't quite work the way RDM desribed it - he missed a step. a == b So, python calls a.__eq__(b) Now, that function does: a.key == b which first calls a.key.__eq__(b) # This step was missing Since str has no idea what an Element is, that returns NotImplemented. Since __eq__ is defined as being commutative, the interpreter then tries b.__eq__(a.key). That function does: b.key == a.key which calls b.key.__eq__(a.key) which is a well defined string comparison and returns the expected answer. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --- ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Getting values stored inside sets
[Nick Coghlan] It doesn't quite work the way RDM desribed it - he missed a step. Thanks for the clarification. We ought to write-out the process somewhere in a FAQ. It may also be instructive to step through the recipe that answers the OP's original request, http://code.activestate.com/recipes/499299/ The call get_equivalent(set([1, 2, 3]), 2.0) wraps the 2.0 in a new object t and calls t in set([1,2,3]). The set.__contains__ method hashes t using t.__hash__(self) and checks for an exact match using t.__eq__(other). Both calls delegate to float objects but the latter also records the other that resulted in a successful equality test (i.e. 2 is the member of the set that matched the 2.0). The get_equivalent call then returns the matching value, 2.0. As far as I can tell, the technique is completely generic and lets you reach inside any function or container to retrieve the other value that is equivalent to self. Raymond ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com