首页 > 编程 > Python > 正文

Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方

2020-02-22 23:15:31
字体:
来源:转载
供稿:网友

本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考,具体如下:

问题:想在某个集合中找出最大或最小的N个元素

解决方案:heapq模块中的nlargest()nsmallest()两个函数正是我们需要的。

>>> import heapq>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]>>> print(heapq.nlargest(3,nums))[42, 37, 23]>>> print(heapq.nsmallest(3,nums))[-4, 1, 2]>>>

这两个函数接受一个参数key,允许其工作在更复杂的数据结构之上:

# example.py## Example of using heapq to find the N smallest or largest itemsimport heapqportfolio = [ {'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'])print(cheap)print(expensive)
Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32Type "copyright", "credits" or "license()" for more information.>>> ================================ RESTART ================================>>>[{'name': 'YHOO', 'price': 16.35, 'shares': 45}, {'name': 'FB', 'price': 21.09, 'shares': 200}, {'name': 'HPQ', 'price': 31.75, 'shares': 35}][{'name': 'AAPL', 'price': 543.22, 'shares': 50}, {'name': 'ACME', 'price': 115.65, 'shares': 75}, {'name': 'IBM', 'price': 91.1, 'shares': 100}]>>>

如果正在寻找的最大或最小的N个元素,且相比于集合中元素的数量,N很小时,下面的函数性能更好。

这些函数首先会在底层将数据转化为列表,且元素会以堆的顺序排列。

>>> import heapq>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]>>> heap=list(nums)>>> heap[1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]>>> heapq.heapify(heap) #heapify()参数必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数。>>> heap[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]>>> heapq.heappop(heap)#如下是为了找到第3小的元素-4>>> heapq.heappop(heap)1>>> heapq.heappop(heap)2>>>

堆(heap)最重要的特性就是heap[0]总是最小的元素。可通过heapq.heappop()轻松找到最小值,这个操作的复杂度为O(logN),N代表堆得大小。

总结:

1、当要找的元素数量相对较小时,函数nlargest()nsmallest()才最适用。
2、若只是想找到最小和最大值(N=1)时,使用min()和max()会更快。

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表