Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考,具体如下:
问题:想在某个集合中找出最大或最小的N个元素
解决方案:heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的。
>>>importheapq >>>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 # #ExampleofusingheapqtofindtheNsmallestorlargestitems importheapq 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=lambdas:s['price']) expensive=heapq.nlargest(3,portfolio,key=lambdas:s['price']) print(cheap) print(expensive)
Python3.4.0(v3.4.0:04f714765c13,Mar162014,19:24:06)[MSCv.160032bit(Intel)]onwin32 Type"copyright","credits"or"license()"formoreinformation. >>>================================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很小时,下面的函数性能更好。
这些函数首先会在底层将数据转化为列表,且元素会以堆的顺序排列。
>>>importheapq >>>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()会更快。
3、若N和集合本身的大小差不多,更快的方法是先对集合排序再进行切片操作(例如使用sorted(items)[:N]或sorted(items)[-N:])
4、heapq.heappush(heap,item):将item压入到堆数组heap中。如果不进行此步操作,后面的heappop()失效;
heapq.heappop(heap):从堆数组heap中取出最小的值,并返回。
heapq.heapify(list):参数必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数。
heapq.heappushpop(heap,item):是上述heappush和heappop的合体,同时完成两者的功能.注意:相当于先操作了heappush(heap,item),然后操作heappop(heap)
heapreplace(heap,item):是heappop(heap)和heappush(heap,item)的联合操作。注意,与heappushpop(heap,item)的区别在于,顺序不同,这里是先进行删除,后压入堆
heap,merge(*iterables)
>>>h=[]#定义一个list >>>fromheapqimport*#引入heapq模块 >>>h [] >>>heappush(h,5)#向堆中依次增加数值 >>>heappush(h,2) >>>heappush(h,3) >>>heappush(h,9) >>>h#h的值 [2,5,3,9] >>>heappop(h)#从h中删除最小的,并返回该值 2 >>>h [3,5,9] >>>h.append(1)#注意,如果不是压入堆中,而是通过append追加一个数值 >>>h#堆的函数并不能操作这个增加的数值,或者说它堆对来讲是不存在的 [3,5,9,1] >>>heappop(h)#从h中能够找到的最小值是3,而不是1 3 >>>heappush(h,2)#这时,不仅将2压入到堆内,而且1也进入了堆。 >>>h [1,2,9,5] >>>heappop(h)#操作对象已经包含了1 1
>>>h [1,2,9,5] >>>heappop(h) 1 >>>heappushpop(h,4)#增加4同时删除最小值2并返回该最小值,与下列操作等同: 2#heappush(h,4),heappop(h) >>>h [4,5,9]
>>>a=[3,6,1] >>>heapify(a)#将a变成堆之后,可以对其操作 >>>heappop(a) 1 >>>b=[4,2,5]#b不是堆,如果对其进行操作,显示结果如下 >>>heappop(b)#按照顺序,删除第一个数值并返回,不会从中挑选出最小的 4 >>>heapify(b)#变成堆之后,再操作 >>>heappop(b) 2
>>>a=[] >>>heapreplace(a,3)#如果list空,则报错 Traceback(mostrecentcalllast): File"",line1,in IndexError:indexoutofrange >>>heappush(a,3) >>>a [3] >>>heapreplace(a,2)#先执行删除(heappop(a)->3),再执行加入(heappush(a,2)) 3 >>>a [2] >>>heappush(a,5) >>>heappush(a,9) >>>heappush(a,4) >>>a [2,4,9,5] >>>heapreplace(a,6)#先从堆a中找出最小值并返回,然后加入6 2 >>>a [4,5,9,6] >>>heapreplace(a,1)#1是后来加入的,在1加入之前,a中的最小值是4 4 >>>a [1,5,9,6]
>>>a=[2,4,6] >>>b=[1,3,5] >>>c=merge(a,b) >>>list(c) [1,2,3,4,5,6]
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。