PyCkBk-2-12

文章来自《Python cookbook》.

翻译仅仅是为了个人学习,其它商业版权纠纷与此无关!

-- Zoom.Quiet [2004-08-11 17:21:08]

1. 在三行代码中展示Quicksort

2.12 Showing Off Quicksort in Three Lines

Credit: Nathaniel Gray

在三行代码中展示Quicksort

1.1. 问题 Problem

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

你需要显示对于功能性程序设计范式来说python的支持比刚看第一眼的时候要好一点。

1.2. 解决 Solution

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

功能性编程语言，Haskell是一个很好的例子，是极好的动物。但是在那样的一伙中python能掌握?br>约骸?

   1 def qsort(L):
   2     if len(L) <= 1: return L
   3     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 is almost as pretty as the Haskell version from target="_blank" href= http://www.haskell.org:>http://www.haskell.org:

在我谦逊的看法中，这是一个几乎和从http://www.haskell.org得到的Haskell版本一样漂亮。

   1 qsort [] = []
   2 qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_ge_x
   3                  where
   4                    elts_lt_x = [y | y <- xs, y < x]
   5                    elts_ge_x = [y | y <- xs, y >= x]

Here's a test function for the Python version:

这里是一个为python版本的测试函数：

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

1.3. 讨论 Discussion

This is a rather naive implementation of quicksort that illustrates the expressive power of list comprehensions. Do not use this in real code! Python's own built-in sort is of course much faster and should always be preferred. 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.

这个是一个相当朴素的quicksort的实现，它展示了list内涵的表现力量。在真实的代码里不用使?br>谜飧觥ython的自己的内建的sort当然也是更快速并且一直是首选的。这个配方唯一合适的使用?br>俏烁笥蚜粝掠∠螅乇鸬兀赜诠δ苄员喑毯虷askell语言，他们（完全可以理解）是热心的 。

I cooked up this function after finding the wonderful Haskell quicksort (which I've reproduced above) at href= http://www.haskell.org/aboutHaskell.html.>http://www.haskell.org/aboutHaskell.htm l. After marveling at the elegance of this code for a while, I realized that list comprehensions made the same thing 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!

在我从http://www.haskell.org/aboutHaskell.html上发现了令人惊奇的Haskell quicksort（在上面我已经展示出来的）以后，我烹调出这个函数。在暂时的为这个代码的优雅大?br>嬷螅胰鲜兜絣ist内涵在python里可能做了相同的事情。我们什么也没做就从Haskell里盗 窃出list内涵，仅仅通过使用关键字而不是标点符号来python化他们

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

依据于list的第一个元素来定的两个实现，对于非常普通的排序一个已经排序的list的情况来看， 都有很不好的O(N2)性能。所以你从不要想着在你的产品代码里去做这个。因为这个仅仅是一个宣?br>锏氖虑椋」芩⒉皇钦娴挠泄叵怠?

List comprehensions were introduced in Python 2.0, so this recipe's code will not work on any earlier version. But then, you wouldn't be trying to impress a friend with a many-years-old version of Python, right?

list内涵在python2.0被介绍，所以这个配方的代码在早期的版本并不工作。但是，你不会用一个?br>芏嗄暌郧暗膒ython来展示它给你的朋友，对吗？

A less compact version with the same architecture can easily be written to use named local variables and functions for enhanced clarity:

为了增加清晰性，一个不太紧凑的具有相同结构的版本能很容易的使用命名的本地变量和函数被写 出来：

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

This one works on old and crusty Python versions, but in Python 2.1 (with a from _ _future_ _ import nested_scopes) and later, you can do without the pivot=pivot trick in the formal argument lists of lt and ge.

1.4. 参考 See Also

The Haskell web site ( http://www.haskell.org).