Guido rethinking removal of cmp from sort method

[Steven D'Aprano]

On Mon, 28 Mar 2011 11:06:20 +0200, Antoon Pardon wrote:

> On Fri, Mar 25, 2011 at 10:40:03PM +0000, Steven D'Aprano wrote:
>> On Fri, 25 Mar 2011 13:56:23 +0100, Antoon Pardon wrote:
>> 
>> > Look we are provided with the cmp_to_key function. If something
>> > doesn't work with that function or performs realy bad with that
>> > function, it means either the function has a bug in it or something
>> > the function relies on, has a bug in it. In either case you just fix
>> > the bug.
>> 
>> No, it means that the trade-offs made by cmp_to_key, or by sorting with
>> a key function, do not interact well with what you are trying to do.
> 
> So and if you find something like that, what stops the dev team from
> saying that python is just not suited to deal with such a problem?

There are lots of problems that Python is not well-suited for.

It is not well-suited for writing the driver to a graphics card.

It is not well-suited to calculating pi to a trillion decimal places.

It is not well-suited for application development on a device with 512K 
of RAM.

It is not well-suited for copying C idioms exactly, or Java, or Perl.

It is not well-suited for doing a lot of bit-twiddling very quickly.

That's why there is more than one programming language: because no one 
language can be well-suited for everything.


[...]
> Asking for *real-world* uses is just how the python community smothers
> requests. 

99% of requests should be smothered. That is a *good thing*. Insisting on 
real-world uses prevents the developers from wasting their valuable time 
bloating Python with thousands of badly desired anti-features that are 
slow, unreliable, buggy, useless or unpopular.


[...]
> Forcing people to use a key-function, will produce cases where python
> will ask for more memory and take longer to sort, than allowing to
> provide a cmp function.

More memory yes; take longer to sort, almost certainly not (except, 
perhaps, for a very narrow window where the addition of a key causes the 
application to page out to virtual memory, but a comparison function 
wouldn't -- and even then, the key function might still be faster).

But we've already covered the "more memory" angle to death. We already 
understand that. This is why I have asked if there are any *other* use-
cases for a comparison function.

Dan Stromberg has suggested that another use-case would be lazy-
comparisons, where you might not be able to generate a single key 
cheaply, but you can perform a comparison lazily.


> This for the simple reason that for some
> order-functions, the only way to write a key-function will be to write a
> specific class, that will implement the order with the same kind of code
> that otherwise would have been put in the cmp function, 

There is a recipe for that on ActiveState's website, google for 
cmp_to_key. That recipe has been added to Python's standard library for 
version 3.2. Please stop flogging that dead horse.


> making the trade off: memory use vs speed no longer a trade off.

You want to use a comparison function: you can still do this. Instead of 
calling

data.sort(cmp=myfunc)

you call

data.sort(key=functools.cmp_to_key(myfunc))

which is a little longer to type, and uses a little more memory, but 
otherwise is no worse than using cmp.


> If the existance alone of such cases isn't enough to reverse the
> decision about the cmp-argument of the sort-method. My guess is that
> nothing will.

Existence of which cases? Made-up imaginary cases that don't actually 
happen? Silly cases that can easily be converted to key comparisons, and 
run much faster if you do so? Trivial cases that can trivially be 
converted to key functions? "I can't be bothered to write a key 
function", to paraphrase one of the posters in this thread -- these are 
hardly convincing.

So far I have one actual use-case: Guido's example of sorting a huge list 
where the amount of time it takes doesn't matter; plus one hypothetical 
but plausible use-case: sorting data where the comparison is expensive 
but lazy. (And to give Carl Banks the benefit of the doubt, one that I 
don't understand, about interfacing with "an obscure C library".)



-- 
Steven