Guido rethinking removal of cmp from sort method

[Steven D'Aprano]

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.

 

[Dave Abrahams]

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

 

[Stefan Behnel]

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

 

[Jean-Michel Pichavant]

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

 

[Steven D'Aprano]

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/[email protected]/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.

 

[Jean-Michel Pichavant]

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/[email protected]/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

 

[Paul Rubin]

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.

 

[Nobody]

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.

 

[Steven D'Aprano]

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/functools.html#functools.cmp_to_key

 

[Paul Rubin]

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.

 

[Ian Kelly]

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.

I would think that you can sort them with key as long as none of the
sequences are equal (which would result in an infinite loop using
either method). Why not this?

_MISSING = object()

@functools.total_ordering
class IteratorKey(object):

def __init__(self, iterable):
self._iterator = iter(iterable)
self._cache = []

def __iter__(self):
# This is not reentrant, but it's
# good enough for this purpose.
for x in self._cache:
yield x
for x in self._iterator:
self._cache.append(x)
yield x

def __lt__(self, other):
for x, y in itertools.izip_longest(self, other, fillvalue=_MISSING):
if x is _MISSING or y is _MISSING:
return x is _MISSING
elif x < y or y < x:
return x < y
return False

def __eq__(self, other):
for x, y in itertools.izip_longest(self, other, fillvalue=_MISSING):
if x is _MISSING or y is _MISSING or x != y:
return False
return True

 

[Paul Rubin]

I would think that you can sort them with key as long as none of the
sequences are equal (which would result in an infinite loop using
either method). Why not this?

Yes you can do something like that, but look how ugly it is compared
with using cmp.

 

[Stefan Behnel]

Paul Rubin, 15.03.2011 09:00:

Yes you can do something like that, but look how ugly it is compared
with using cmp.

I would argue that it's a rare use case, though. In most cases, memory
doesn't really matter, and the overhead of a decorated sort is acceptable.
In some cases, where space matters, an external sort is a better choice or
even the only thing that will work, so all that's left are the cases where
speed really needs to be traded for space *and* an external sort is not
applicable, and those where things can be expressed more easily using cmp
than using a key. For the latter, there's support in the standard library,
as Steven pointed out. Now, the question that remains is: are the few
remaining cases worth being supported directly, thus complicating the
internal source code of the Python runtime?

Stefan

 

[Paul Rubin]

the question that remains is: are the few remaining cases worth being
supported directly, thus complicating the internal source code of the
Python runtime?

The other cases were supported perfectly well already, and the support
was removed. That's just ludicrous in my opinion.

 

[Antoon Pardon]

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.

How about a list of tuples where you want them sorted first item in ascending
order en second item in descending order.

 

[Stefan Behnel]

Antoon Pardon, 23.03.2011 14:53:

How about a list of tuples where you want them sorted first item in ascending
order en second item in descending order.

You can use a stable sort in two steps for that.

Stefan

 

[Antoon Pardon]

Antoon Pardon, 23.03.2011 14:53:

You can use a stable sort in two steps for that.

Which isn't helpfull if where you decide how they have to be sorted is
not the place where they are actually sorted.

I have a class that is a priority queue. Elements are added at random but
are removed highest priority first. The priority queue can have a key or
a cmp function for deciding which item is the highest priority. It
can also take a list as an initializor, which will then be sorted.

So this list is sorted within the class but how it is sorted is decided
outside the class. So I can't do the sort in multiple steps.

 

[Ian Kelly]

Which isn't helpfull if where you decide how they have to be sorted is
not the place where they are actually sorted.

I have a class that is a priority queue. Elements are added at random but
are removed highest priority first. The priority queue can have a key or
a cmp function for deciding which item is the highest priority. It
can also take a list as an initializor, which will then be sorted.

So this list is sorted within the class but how it is sorted is decided
outside the class. So I can't do the sort in multiple steps.

You can't do this?

for (key, reversed) in self.get_multiple_sort_keys():
self.pq.sort(key=key, reversed=reversed)

 

[Stefan Behnel]

Antoon Pardon, 23.03.2011 16:14:

Which isn't helpfull if where you decide how they have to be sorted is
not the place where they are actually sorted.

I have a class that is a priority queue. Elements are added at random but
are removed highest priority first. The priority queue can have a key or
a cmp function for deciding which item is the highest priority. It
can also take a list as an initializor, which will then be sorted.

So this list is sorted within the class but how it is sorted is decided
outside the class. So I can't do the sort in multiple steps.

That sounds more like a use case for heap sort than for Python's builtin
list sort. See the heapq module.

Stefan

 

[Carl Banks]

Antoon Pardon, 23.03.2011 14:53:



You can use a stable sort in two steps for that.

How about this one: you have are given an obscure string collating
function implented in a C library you don't have the source to.

Or how about this: I'm sitting at an interactive session and I have a
convenient cmp function but no convenient key, and I care more about
the four minutes it'd take to whip up a clever key function or an
adapter class than the 0.2 seconds I'd save to on sorting time.

Removing cmp from sort was a mistake; it's the most straightforward
and natural way to sort in many cases. Reason enough for me to keep
it.


Carl Banks