Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Guido rethinking removal of cmp from sort method

Reply
Thread Tools

Guido rethinking removal of cmp from sort method

 
 
Steven D'Aprano
Guest
Posts: n/a
 
      03-13-2011
The removal of cmp from the sort method of lists is probably the most
disliked change in Python 3. On the python-dev mailing list at the
moment, Guido is considering whether or not it was a mistake.

If anyone has any use-cases for sorting with a comparison function that
either can't be written using a key function, or that perform really
badly when done so, this would be a good time to speak up.



--
Steven
 
Reply With Quote
 
 
 
 
Dave Abrahams
Guest
Posts: n/a
 
      03-13-2011
Steven D'Aprano <steve+comp.lang.python <at> pearwood.info> writes:

> If anyone has any use-cases for sorting with a comparison function that
> either can't be written using a key function, or that perform really
> badly when done so, this would be a good time to speak up.


I think it's probably provable that there are no cases in the first category,
provided you're willing to do something sufficiently contorted. However,
it also seems self-evident to me that many programmers will rightly chafe
at the idea of creating and tearing down a bunch of objects just to
compare things for sorting. Think of the heap churn! Even if it turns out
that Python 3 contains some magic implementation detail that makes it
efficient most of the time, it goes against a natural understanding of the
computation model

2p for y'all.
-Dave

 
Reply With Quote
 
 
 
 
Stefan Behnel
Guest
Posts: n/a
 
      03-14-2011
Steven D'Aprano, 13.03.2011 13:59:
> The removal of cmp from the sort method of lists is probably the most
> disliked change in Python 3. On the python-dev mailing list at the
> moment, Guido is considering whether or not it was a mistake.
>
> If anyone has any use-cases for sorting with a comparison function that
> either can't be written using a key function, or that perform really
> badly when done so, this would be a good time to speak up.


As Raymond Hettinger and Daniel Stutzbach pointed out in that thread, the
memory overhead is much lower in Python 3.2 and also depends on the usage.
If memory is a problem, it can still be traded for time by sorting in
multiple (stable) passes with smaller keys. It rarely is a problem in
practice, though, and Guido's initial post seems to suggest that as well.

Stefan

 
Reply With Quote
 
Jean-Michel Pichavant
Guest
Posts: n/a
 
      03-14-2011
Steven D'Aprano wrote:
> The removal of cmp from the sort method of lists is probably the most
> disliked change in Python 3. On the python-dev mailing list at the
> moment, Guido is considering whether or not it was a mistake.
>
> If anyone has any use-cases for sorting with a comparison function that
> either can't be written using a key function, or that perform really
> badly when done so, this would be a good time to speak up.
>
>
>
>

You seem concerned by this removal, do you have any use-case ?

JM
 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      03-14-2011
On Mon, 14 Mar 2011 12:10:27 +0100, Jean-Michel Pichavant wrote:

> Steven D'Aprano wrote:
>> The removal of cmp from the sort method of lists is probably the most
>> disliked change in Python 3. On the python-dev mailing list at the
>> moment, Guido is considering whether or not it was a mistake.
>>
>> If anyone has any use-cases for sorting with a comparison function that
>> either can't be written using a key function, or that perform really
>> badly when done so, this would be a good time to speak up.
>>
>>
>>
>>

> You seem concerned by this removal, do you have any use-case ?


You seem concerned by my concern. Why do you think I am concerned?

(1) I'm not concerned, but many people are. If you search the archives of
this newsgroup (mailing list), you'll see that I have defended the
removal of cmp from sort, e.g. this post:

http://www.mail-archive.com/python-l...msg261728.html


(2) If I had a good use-case for keeping cmp, I wouldn't need to ask
others if they had a good use-case.

As it is, Guido himself has mentioned one such good use for a comparison
function when sorting. Use of a key function trades off memory for time,
while sorting with a comparison function makes the opposite trade off,
using more time for the sake of saving memory.



--
Steven
 
Reply With Quote
 
Jean-Michel Pichavant
Guest
Posts: n/a
 
      03-14-2011
Steven D'Aprano wrote:
> On Mon, 14 Mar 2011 12:10:27 +0100, Jean-Michel Pichavant wrote:
>
>
>> Steven D'Aprano wrote:
>>
>>> The removal of cmp from the sort method of lists is probably the most
>>> disliked change in Python 3. On the python-dev mailing list at the
>>> moment, Guido is considering whether or not it was a mistake.
>>>
>>> If anyone has any use-cases for sorting with a comparison function that
>>> either can't be written using a key function, or that perform really
>>> badly when done so, this would be a good time to speak up.
>>>
>>>
>>>
>>>
>>>

>> You seem concerned by this removal, do you have any use-case ?
>>

>
> You seem concerned by my concern. Why do you think I am concerned?
>
> (1) I'm not concerned, but many people are. If you search the archives of
> this newsgroup (mailing list), you'll see that I have defended the
> removal of cmp from sort, e.g. this post:
>
> http://www.mail-archive.com/python-l...msg261728.html
>
>
> (2) If I had a good use-case for keeping cmp, I wouldn't need to ask
> others if they had a good use-case.
>
> As it is, Guido himself has mentioned one such good use for a comparison
> function when sorting. Use of a key function trades off memory for time,
> while sorting with a comparison function makes the opposite trade off,
> using more time for the sake of saving memory.
>
>

Just to know if currently the use-case count is zero. Nothing evil
hidden behind my question

JM



 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      03-14-2011
Steven D'Aprano <(E-Mail Removed)> writes:
> If anyone has any use-cases for sorting with a comparison function that
> either can't be written using a key function, or that perform really
> badly when done so, this would be a good time to speak up.


We've had this discussion a couple times before. I remember an example
involving comparing tree structures, that I thought couldn't be done
with key= in a reasonable way, and that this was a reasonable real-world
example. Raymond H then gave a way of encoding it with key= which
looked ok at the time, but I decided sometime later that I think we both
missed an error in that encoding, so I've been wanting to dig it out
again and look more closely.

key= can of course burn a lot more memory because of the DSU pattern
(say you are sorting file handles according to the contents of the file,
so with key= you might have to read N multi-megabyte files where with
cmp you just pairwise-compare them until they differ, which is probably
in the first few bytes).

Finally I concocted an "infinite" example which we agreed is artificial:
you are given a list of generators denoting real numbers, for example
pi generates the infinite sequence 3,1,4,1,5,9... while e generates
2,7,1,8,... You can sort these with cmp but not with key.
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      03-14-2011
On Mon, 14 Mar 2011 12:39:35 -0700, Paul Rubin wrote:

> Finally I concocted an "infinite" example which we agreed is artificial:
> you are given a list of generators denoting real numbers, for example
> pi generates the infinite sequence 3,1,4,1,5,9... while e generates
> 2,7,1,8,... You can sort these with cmp but not with key.


Is there some restriction on the return type of the key= function? If not,
you can define a class with appropriate comparison methods and have key=
return instances of that class.

 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      03-15-2011
On Mon, 14 Mar 2011 23:37:06 +0000, Nobody wrote:

> On Mon, 14 Mar 2011 12:39:35 -0700, Paul Rubin wrote:
>
>> Finally I concocted an "infinite" example which we agreed is
>> artificial: you are given a list of generators denoting real numbers,
>> for example pi generates the infinite sequence 3,1,4,1,5,9... while e
>> generates 2,7,1,8,... You can sort these with cmp but not with key.

>
> Is there some restriction on the return type of the key= function? If
> not, you can define a class with appropriate comparison methods and have
> key= return instances of that class.


You mean like this?

http://docs.python.org/dev/library/f...ols.cmp_to_key




--
Steven
 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      03-15-2011
Nobody <(E-Mail Removed)> writes:
>> 2,7,1,8,... You can sort these with cmp but not with key.

>
> Is there some restriction on the return type of the key= function? If not,
> you can define a class with appropriate comparison methods and have key=
> return instances of that class.


Sorry, yeah, of course you can do it that way, but it's bloody ugly and
you're no longer gaining the supposed benefit of the DSU pattern.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Q: sort's key and cmp parameters kj Python 45 10-07-2009 05:15 PM
TODAY April 4 -Guido & Python 3000 @ Global FSW Voice MeetingBerkeleyTIP -Linus,Guido,Shuttleworth... john_re Python 0 04-04-2009 08:00 AM
Using s.sort([cmp[, key[, reverse]]]) to sort a list of objects based on a attribute cjt22@bath.ac.uk Python 7 09-10-2007 11:10 AM
basic questions on cmp, < and sort =?ISO-8859-1?Q?Sch=FCle_Daniel?= Python 4 10-26-2006 06:48 AM
no cmp field defined in cmp ejb Andrea Sansottera Java 0 07-16-2004 02:24 PM



Advertisments