5.8 获取序列中最小的几个元素
感谢：Matteo Dell'Amico、Raymond Hettinger、George Yoshida、Daniel Harding
任务
你需要从一个给定的序列中获取一些最小的元素。可以将序列排序，然后使用seq[:n]，但还有没有更好的办法呢？
解决方案
如果需要的元素数目n远小于序列的长度，也许还能做得更好。sort是很快的，但它的时间复杂度仍然是O(nlogn)，但如果n很小，我们获取前n个最小元素的时间是O(n)。下面给出一个简单可行的生成器，在Python 2.3和2.4中都同样有效：
- import heapq
- def isorted(data):
- data = list(data)
- heapq.heapify(data)
- while data:
- yield heapq.heappop(data)
在Python 2.4中，如果事先知道n，还有更简单和更快的方法从data中获取前n个最小的元素：
- import heapq
- def smallest(n, data):
- return heapq.nsmallest(n, data)
讨论
data可能是任何有边界的可迭代对象，解决方案中的isorted函数通过调用list来确保它是序列。也可以删掉data = list(data)这一行，假如下列条件满足的话：你知道data是一个序列，你并不关心生成器是否重新排列了data的元素，而且需要在获取的同时从data中删除元素。
如同5.7节所示，Python标准库提供了heapq模块，它支持人们熟知的数据结构- 堆。解决方案中的isorted先创建了一个堆（通过heap.heapify），然后在每一步获取元素的时候（通过heap.heappop），生成并删除堆中最小的元素。
在Python 2.4中，heapq模块引入了两个新函数。heapq.nlargest (n, data) 返回的是一个长度为n的data中最大的元素的列表，heapq.nsmallest (n, data) 则返回一个包含前n个最小元素的列表。这些函数并不要求data满足堆的条件，它们甚至不要求data是一个列表-任何有边界的、元素是可以比较的可迭代对象都适用。解决方案中的函数smallest除了调用heapq.smallest，其实什么也没干。
关于速度，我们总是应该进行实际测量，猜测不同代码片段的相对运行速度是毫无意义的行为。因此，当我们只是循环获取前几个（最小）元素的时候，isorted的性能和Python 2.4内建的sorted函数的性能比起来究竟怎么样呢？为了进行测试，我写了一个top10函数，它可以调用这两种方法，然后我也为Python 2.3实现了一个sorted函数，因为在Python 2.3中此函数并未得到原生的支持：
- try:
- sorted
- except:
- def sorted(data):
- data = list(data)
- data.sort( )
- return data
- import itertools
- def top10(data, howtosort):
- return list(itertools.islice(howtosort(data), 10))
在我的计算机上，在Python 2.4中处理一个洗过牌的1 000个整数的列表，top10调用isorted耗时260 s，但采用内建的sorted则耗时850 s。而Python 2.3甚至还要慢得多：isorted耗时12ms，sorted耗时2.7ms。换句话说，Python 2.3的sorted比Python 2.4的sorted要慢3倍，但在isorted上则要慢50倍。需要记住这个重要的经验：当需要进行优化时，首先进行测量。不应该仅仅根据基本原理选择优化的方式，因为真实的性能数据变化多端，即使在两个兼容的发行版本之间也会有很大的差异。第二个经验是：如果真的很关心性能，那赶紧转移到Python 2.4吧。和Python 2.3相比，Python 2.4经过了极大的优化和加速，特别是在搜索和排序的方面。
如果确定你的代码只需要支持Python 2.4，那么，如同本节解决方案所建议的那样，应当使用heapq的新函数nsmallest。它速度快、使用简便，远胜于自己编写代码。举个例子，实现Python 2.4中的top10，你只需要：
- import heapq
- def top10(data):
- return heapq.nsmallest(10, data)
比起前面展示的那个基于isorted的top10，对同样的洗过牌的1 000个整数的列表进行处理，消耗的时间还可以削减一半。
更多资料
Library Reference和Python in a Nutshell中list类型的sort方法，以及heapq和timeit模块；第19章中关于Python的迭代的内容；Python in a Nutshell中有关优化的章节；Python源码中的heap.py所包含的关于堆的有趣的讨论；5.7节关于heapq的介绍。