|
楼主 |
发表于 2015-5-9 00:57:25
|
显示全部楼层
问题:怎样从一个集合中获得最大或者最小的N个元素列表?
解决:heapq模块有两个函数:nlargest() 和 nsmallest() 可以完美解决这个问题。
- import heapq
- nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
- print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
- print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]
复制代码 两个函数都能接受一个关键字参数,用于更复杂的数据结构中:
- portfolio = [
- {'name': 'IBM', 'shares': 100, 'price': 91.1},
- {'name': 'AAPL', 'shares': 50, 'price': 543.22},
- {'name': 'FB', 'shares': 200, 'price': 21.09},
- {'name': 'HPQ', 'shares': 35, 'price': 31.75},
- {'name': 'YHOO', 'shares': 45, 'price': 16.35},
- {'name': 'ACME', 'shares': 75, 'price': 115.65}
- ]
- cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
- expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
复制代码 PS:这个参数key,用max和min两个函数用的多的同学相信比较熟悉了,不懂的,先去看看max和min两个函数的key参数,举一反三,这里的key参数是同样 的用法
根据原书中的说法,这两个函数实际上是对列表中的元素进行了堆排序,堆是一种数据结构, 基本上只要是数据结构和算法书籍里面都会有提及到,不知道甲鱼小哥的数据结构视频中有否提到,但它确实一种很有用的数据结构,由其是这个问题中所遇到的情况。
另外,你可以用heapq.heapify()函数将一个列表转化为堆,转化为堆后,列表的第一个元素是最小的元素
- >>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
- >>> import heapq
- >>> heapq.heapify(nums)
- >>> nums
- [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
- >>>
复制代码 另外 ,你可以用heapq.heappop()函数弹出最小的元素,并将剩下的元素依然保持为堆结构,换句话说,该函数会先将第一个元素弹出来,然后用下一个最小的元素来取代被弹出元素(这种操作时间复杂度仅仅是O(N),N是堆大小,这里的时间复杂度指的是最坏情况下的时间复杂度)。这样我们想找最小的三个元素只需要调用三次heapq.heappop()函数即可
最后,书的作者提醒我们nlargest() 和 nsmallest()这两个函数在你需要找的元素远小于总元素个数时,效率不错,但当你要找的元素个数接近总元素个数时,用这两个函数不如你直接排序加列表切片来的实在,正如作者所说在正确的场合使用正确的工具才能让你的工作进行的更有效率。
|
|