[Python-Dev] Incorrect length of collections.Counter objects / Multiplicity function
Hello, everyone. I've checked the new collections.Counter class and I think I've found a bug: > >>> from collections import Counter > >>> c1 = Counter([1, 2, 1, 3, 2]) > >>> c2 = Counter([1, 1, 2, 2, 3]) > >>> c3 = Counter([1, 1, 2, 3]) > >>> c1 == c2 and c3 not in (c1, c2) > True > >>> # Perfect, so far. But... There's always a "but": > ... > >>> len(c1) > 3 The length of a Counter is the amount of unique elements. But the length must be the cardinality, and the cardinality of a multiset is the total number of elements (including duplicates) [1] [2]. The source code mentions that the recipe on ActiveState [3] was one of the references, but that recipe has this right. Also, why is it indexed? The indexes of a multiset call to mind the position of its elements, but there's no such thing in sets. I think this is inconsistent with the built-in set. I would have implemented the multiplicity function as a method instead of the indexes: c1.get_multiplicity(element) # instead of c1[element] Is this the intended behavior? If so, I'd like to propose a proper multiset implementation for the standard library (preferably called "Multiset"; should I create a PEP?). If not, I can write a patch to fix it, although I'm afraid it'd be a backwards incompatible change. Cheers, [1] http://en.wikipedia.org/wiki/Multiset#Overview [2] http://preview.tinyurl.com/smalltalk-bag [3] http://code.activestate.com/recipes/259174/ -- Gustavo Narea . | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | ___ 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
[Python-Dev] Unordered tuples/lists
Hello, everybody. I've been searching for a data structure like a tuple/list *but* unordered -- like a set, but duplicated elements shouldn't be removed. I have not even found a recipe, so I'd like to write an implementation and contribute it to the "collections" module in the standard library. This is the situation I have: I have a data structure that represents an arithmetic/boolean operation. Operations can be commutative, which means that the order of their operands don't change the result of the operation. This is, the following operations are equivalent: operation(a, b, c) == operation(c, b, a) == operation(b, a, c) operation(a, b, a) == operation(a, a, b) == operation(b, a, a) operation(a, a) == operation(a, a) So, I need a type to store the arguments/operands so that if two of these collections have the same elements with the same multiplicity, they are equivalent, regardless of the order. A multiset is not exactly what I need: I still need to use the elements in the order they were given. For example, the logical conjuction (aka "and" operator) has a left and right operands; I need to evaluate the first/left one and, if it returned True, then call the second/right one. They must not be evaluated in a random order. To sum up, it would behave like a tuple or a list, except when it's compared with another object: They would be equivalent if they're both unordered tuples/lists, and have the same elements. There can be mutable and immutable editions (UnorderedList and UnorderedTuple, respectively). I will write a PEP to elaborate on this if you think it'd be nice to have. Or, should I have written the PEP first? Cheers, -- Gustavo Narea . | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | ___ 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] Unordered tuples/lists
Hi, Guido. On Wed, May 19, 2010 at 12:11 AM, Guido van Rossum wrote: > This is typically called a "bag". Maybe searching for that will help > you find a recipe? > A bag/multiset is close to what I need, except for one thing: I need to iterate over the elements in the original order, not in a random order. The data structure I'm proposing is basically a list/tuple, and the only thing that changes is comparison with another unordered list/tuple: If they both have the same elements with the same multiplicity, they are equivalent (regardless of the order). Cheers, - Gustavo. ___ 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] Unordered tuples/lists
Hello, Oleg. > class UnorderedList(list): >def __eq__(self, other): >if not isinstance(other, UnorderedList): >return False >return sorted(self) == sorted(other) > >def __ne__(self, other): >return not self.__eq__(other) > > Do you need more than that? > > Oleg. That's what I had in mind. I think it'd be useful enough to go in the standard library. Now that there's a sample implementation, should I still try to demonstrate why I believe it's worth adding to the stdlib and get support? Cheers, - Gustavo. On Tue, May 18, 2010 at 11:13 PM, Gustavo Narea wrote: > Hello, everybody. > > I've been searching for a data structure like a tuple/list *but* unordered > -- > like a set, but duplicated elements shouldn't be removed. I have not even > found a recipe, so I'd like to write an implementation and contribute it to > the "collections" module in the standard library. > > This is the situation I have: I have a data structure that represents an > arithmetic/boolean operation. Operations can be commutative, which means > that > the order of their operands don't change the result of the operation. This > is, > the following operations are equivalent: >operation(a, b, c) == operation(c, b, a) == operation(b, a, c) >operation(a, b, a) == operation(a, a, b) == operation(b, a, a) >operation(a, a) == operation(a, a) > > So, I need a type to store the arguments/operands so that if two of these > collections have the same elements with the same multiplicity, they are > equivalent, regardless of the order. > > A multiset is not exactly what I need: I still need to use the elements in > the > order they were given. For example, the logical conjuction (aka "and" > operator) has a left and right operands; I need to evaluate the first/left > one > and, if it returned True, then call the second/right one. They must not be > evaluated in a random order. > > To sum up, it would behave like a tuple or a list, except when it's > compared > with another object: They would be equivalent if they're both unordered > tuples/lists, and have the same elements. There can be mutable and > immutable > editions (UnorderedList and UnorderedTuple, respectively). > > I will write a PEP to elaborate on this if you think it'd be nice to have. > Or, > should I have written the PEP first? > > Cheers, > -- > Gustavo Narea . > | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | > ___ 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] Unordered tuples/lists
Martin said: > Most definitely. Just in case it isn't clear: nobody else seems to think > this is useful (let alone useful enough to go into the standard > library). In addition, it's trivial to implement, more reason not to add > it. Yeah, fair enough. Thanks for your responses! :) -- Gustavo Narea . | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | ___ 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] Incorrect length of collections.Counter objects / Multiplicity function
Anyone? Gustavo said: > Hello, everyone. > > I've checked the new collections.Counter class and I think I've found a bug: > > >>> from collections import Counter > > >>> c1 = Counter([1, 2, 1, 3, 2]) > > >>> c2 = Counter([1, 1, 2, 2, 3]) > > >>> c3 = Counter([1, 1, 2, 3]) > > >>> c1 == c2 and c3 not in (c1, c2) > > > > True > > > > >>> # Perfect, so far. But... There's always a "but": > > ... > > > > >>> len(c1) > > > > 3 > > The length of a Counter is the amount of unique elements. But the length > must be the cardinality, and the cardinality of a multiset is the total > number of elements (including duplicates) [1] [2]. The source code > mentions that the recipe on ActiveState [3] was one of the references, but > that recipe has this right. > > Also, why is it indexed? The indexes of a multiset call to mind the > position of its elements, but there's no such thing in sets. I think this > is inconsistent with the built-in set. I would have implemented the > multiplicity function as a method instead of the indexes: > c1.get_multiplicity(element) > # instead of > c1[element] > > Is this the intended behavior? If so, I'd like to propose a proper multiset > implementation for the standard library (preferably called "Multiset"; > should I create a PEP?). If not, I can write a patch to fix it, although > I'm afraid it'd be a backwards incompatible change. > > Cheers, > > [1] http://en.wikipedia.org/wiki/Multiset#Overview > [2] http://preview.tinyurl.com/smalltalk-bag > [3] http://code.activestate.com/recipes/259174/ -- Gustavo Narea . | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | ___ 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
[Python-Dev] Releases for recent security vulnerability
Hi all, How come a description of how to exploit a security vulnerability comes before a release for said vulnerability? I'm talking about this: http://blog.python.org/2011/04/urllib-security-vulnerability-fixed.html My understanding is that the whole point of asking people not to report security vulnerability publicly was to allow time to release a fix. If developers haven't had enough time to release the fix, that's fine. But I can't think of a sensible reason why it should be announced first. Cheers, - Gustavo. ___ 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] Releases for recent security vulnerability
Hello, On 15/04/11 13:30, Brian Curtin wrote: > To me, the fix *was* released. No, it wasn't. It was *committed* to the repository. > Sure, no fancy installers were generated yet, but people who are > susceptible to this issue 1) now know about it, and 2) have a way to > patch their system *if needed*. Well, that's a long shot. I doubt the people/organizations affected are all aware. And I doubt they are all capable of patching their system or getting a patched Python from a trusted party. Three weeks after this security vulnerability was *publicly* reported on bugs.python.org, and two days after it was semi-officially announced, I'm still waiting for security updates for my Ubuntu and Debian systems! I reckon if this had been handled differently (i.e., making new releases and communicating it via the relevant channels [1]), we wouldn't have the situation we have right now. May I suggest that you adopt a policy for handling security issues like Django's? http://docs.djangoproject.com/en/1.3/internals/contributing/#reporting-security-issues Cheers, [1] For example, <http://mail.python.org/mailman/listinfo/python-announce-list>, <http://www.python.org/news/>, <http://www.python.org/news/security/>. -- Gustavo Narea . | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about | ___ 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
