Guido rethinking removal of cmp from sort method

Paul Rubin no.email at nospam.invalid
Mon Mar 14 15:39:35 EDT 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.

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.



More information about the Python-list mailing list