Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

Recipe 5.11. Showing off quicksort in Three Lines

Credit: Nathaniel Gray, Raymond Hettinger, Christophe
Delord, Jeremy Zucker

Problem

You need to show that
Python's support for the functional programming
paradigm is better than it might seem at first sight.

Solution

Functional programming languages, of which Haskell is a great
example, are splendid animals, but Python can hold its own in such
company:

def qsort(L):
if len(L) <= 1: return L
return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + 
qsort([ge for ge in L[1:] if ge >= L[0]])

In my humble opinion, this code is almost as pretty as the Haskell
version from http://www.haskell.org:

qsort [  ] = [  ]
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]

Here's a test function for the Python version:

def qs_test(length):
import random
joe = range(length)
random.shuffle(joe)
qsJoe = qsort(joe)
for i in range(len(qsJoe)):
assert qsJoe[i] == i, 'qsort is broken at %d!' %i

Discussion

This rather naive implementation of
quicksort illustrates the expressive power of list comprehensions. Do
not use this approach in real code! Python lists have an in-place
sort method that is much faster and should always
be preferred; in Python 2.4, the new built-in function
sorted accepts any finite sequence and returns a
new sorted list with the sequence's items. The only
proper use of this recipe is for impressing friends, particularly
ones who (quite understandably) are enthusiastic about functional
programming, and particularly about the Haskell language.

I cooked up this function after finding the wonderful Haskell
quicksort (which I've reproduced in the
"Solution") at http://www.haskell.org/aboutHaskelll.
After marveling at the elegance of this code for a while, I realized
that list comprehensions made the same approach possible in Python.
Not for nothing did we steal list comprehensions right out of
Haskell, just Pythonizing them a bit by using keywords rather than
punctuation!

Both implementations pivot on the first element of the list and thus
have worst-case O(n) performance for the very
common case of sorting an already sorted list. You would never want
to do so in production code! Because this recipe is just a propaganda
piece, though, it doesn't really matter.

You can write a less compact version with similar architecture in
order to use named local variables and functions for enhanced
clarity:

def qsort(L):
if not L: return L
pivot = L[0]
def lt(x): return x<pivot
def ge(x): return x>=pivot
return qsort(filter(lt, L[1:]))+[pivot]+qsort(filter(ge, L[1:]))

Once you start going this route, you can easily move to a slightly
less naive version, using random pivot selection to make worst-case
performance less likely and counting pivots to handle degenerate case
with many equal elements:

import random
def qsort(L):
if not L: return L
pivot = random.choice(L)
def lt(x): return x<pivot
def gt(x): return x>pivot
return qsort(filter(lt, L))+[pivot]*L.count(pivot)+qsort(filter(gt, L))

Despite the enhancements, they are meant essentially for fun and
demonstration purposes. Production-quality sorting code is quite
another thing: these little jewels, no matter how much we dwell on
them, will never match the performance and solidity of
Python's own built-in sorting approaches.

Rather than going for clarity and robustness, we can move in the
opposite direction to make this last point most obvious, showing off
the obscurity and compactness that one can get with
Python's lambda:

q=lambda x:(lambda o=lambda s:[i for i in x if cmp(i,x[0])==s]:
len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x)( )

At least, with this beauty (a single logical
line, although it needs to be split into two physical lines due to
its length), it should be absolutely obvious that this approach is
not meant for real-world use. The equivalent, using more readable
def statements rather than opaque
lambdas, would still be pretty obscure:

def q(x):
def o(s): return [i for i in x if cmp(i,x[0])==s]
return len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x

but a little more clarity (and sanity) can be recovered by opening up
the pithy len(x)>1 and . . . or x into an
if/else statement and
introducing sensible local names again:

def q(x):
if len(x)>1:
lt = [i for i in x if cmp(i,x[0]) == -1 ]
eq = [i for i in x if cmp(i,x[0]) == 0 ]
gt = [i for i in x if cmp(i,x[0]) == 1 ]
return q(lt) + eq + q(gt)
else:
return x

Fortunately, in the real world, Pythonistas are much too sensible to
write convoluted, lambda-filled horrors such as
this. In fact, many (though admittedly not all) of us feel enough
aversion to lambda itself (partly from having seen
it abused this way) that we go out of our way to use readable
def statements instead. As a result, the ability
to decode such "bursts of line
noise" is not a necessary
survival skill in the Python world, as it might be for other
languages. Any language feature can be abused by
programmers trying to be "clever" .
. . as a result, some Pythonistas (though a minority) feel a similar
aversion to features such as list comprehensions (since
it's possible to cram too many things into a list
comprehension, where a plain for loop would be
clearer) or to the short-circuiting behavior of operators
and/or (since they can be
abused to write obscure, terse expressions where a plain
if statement would be clearer).

See Also

The Haskell web site, http://www.haskell.org.