2010-01-27

python 3 sort

On Jan 26, 3:47 pm, Xah Lee wrote:

> * Many functions that return lists now returns “Views” or
> “Iterators” Instead. A fucking fuck all fucked up shit. A extraneous
> “oop engineering” complication. (See: Lambda in Python 3000)

See also:

“Iterators: Signs of Weakness in Object-Oriented Languages” (1992) By Henry G Baker. http://home.pipeline.com/~hbaker1/Iterator.html

Xah wrote:
> * The cmp() function used in sort is basically gone, users are now
> supposed to use the “key” parameter instead. This is a flying-face-
> fuck to computer science. This would be the most serious fuckup in
> python 3. (See: Sorting in Python and Perl)

Steven D'Aprano wrote:
> I did too, when I first heard cmp was to be dumped. But I changed my mind
> and now agree with the decision to drop cmp. Custom sorts are nearly
> always much better written with key rather than cmp: key adds an O(N)
> overheard to the sorting, while cmp makes sorting O(N**2). In other
> words, key is *much* faster, and generally easier to write as well.

The reason cmp is a order slower is due to Python lang's limitation and compiler implementation limitation.

• Sorting in Python and Perl
http://xahlee.org/perl-python/sort_list.html

the python lang, by the very nature of being a dynamic lang, makes it hard for compiler analize and optimize a sort function call with cmp argument that is equivalent to a key.

So, for practical reasons, i think a “key” parameter is fine. But chopping off “cmp” is damaging. When your data structure is complex, its order is not embedded in some “key”. Taking out “cmp” makes it impossible to sort your data structure.

in the essay, i also gave a few examples of data structures where you need a general means to specify the ordering function in order to sort. Without a cmp, you'll need to munge your data by some decorate-sort-dedecorate technique.

From another perspective, often it is considered a good principle of design that the lang be a bit flexible to let programers do what they want, instead of force them into one way. Python, being a loosely typed lang, with so-called “duck typing”, in contrast to Java or OCaml in different ways, certainly is more on the lose extreme of the lang spectrum with respect to code construction. So, i don't see how python 3 people made the decision to removed cmp. (am pretty sure, at least part of the reason, is a ill attitude towards functional programing and lambda, lead by Guido.)

> There may be a handful of rare applications where there is no obvious way
> to convert a cmp function to a key, but they are vanishingly rare. I
> think, if you search the archives, Paul Rubin may have come up with one
> example. There are a number of recipes for easily converting cmp sorts to
> key sorts.

You say that it is rare. You are probably right. Though, that may just be caused by the language itself and consequently the type of people who uses it. If Python's lambda is not limited, and the python community doesn't look down on lambda, it is likely cmp will used more. The more your data structure becomes complex, the more cmp will be needed.

> I think, in my perfect world, list.sort() and sorted() should continue
> being key based, while the standard library contained (perhaps in the
> functools module?) a sort function that contains all the bells and
> whistles. You want cmp, it's there, and you can pay the extra cost if you
> need it. You want to sort multiple lists by the contents of one? One
> import away. But keep the general sort() function lean and super-fast.

btw, is something like cmp still available in some module for sort?

Xah
∑ http://xahlee.org/