Guido rethinking removal of cmp from sort method

[Steven D'Aprano]

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.

An analogy: Python lists are contiguous arrays of pointers. When the 
array is full, Python automatically doubles the size of the list. This is 
a good trade-off of space (memory) for time, because it means that list 
access is O(1), searching is O(N), and appending is O(1) on average. At 
worst, you waste 50% of the memory used, which is pretty good.

But if you're programming for a device with 8 K of memory (if such a 
thing even exists these days!), this would be a *terrible* strategy. 
(Python wouldn't even fit in 8K, but never mind that...) In this case, 
memory is more precious than programmer convenience, or even execution 
speed. It's not enough to hand-wave and say "Python lists have a bug that 
needs fixing", because that's simply not the case. It's that the design 
of Python lists doesn't suit the use-case, and if you try it, it will 
perform badly or not at all: by design, Python lists assume memory will 
be plentiful and time will be short.

That is exactly the same trade-off key-based sorting makes: it uses more 
memory to speed up sorting. This is a good strategy for Python, because 
Python already requires lots of memory (so no major loss there), and is a 
rather slow language (so speed-ups help).

So the question is, being completely general, as there any *real-world* 
(not artificial, made-up) uses where sorting with a comparison function 
works but a key function doesn't? I'm not limiting you to cases where you 
have a shortage of memory but lots of time available. There may be other 
design choices where key-based sorting sucks. We already know that some 
people just prefer the look and feel of writing and using cmp functions. 
Is there anything else?



-- 
Steven