本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考,具体如下:
问题:想在某个集合中找出最大或最小的N个元素
解决方案:heapq模块中的nlargest()
和nsmallest()
两个函数正是我们需要的。
1
2
3
4
5
6
7
|
>>> 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,允许其工作在更复杂的数据结构之上:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# example.py
#
# Example of using heapq to find the N smallest or largest items
import heapq
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' ])
print (cheap)
print (expensive)
|
1
2
3
4
5
6
7
|
Python 3.4 . 0 (v3. 4.0 : 04f714765c13 , Mar 16 2014 , 19 : 24 : 06 ) [MSC v. 1600 32 bit (Intel)] on win32
Type "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很小时,下面的函数性能更好。
这些函数首先会在底层将数据转化为列表,且元素会以堆的顺序排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
>>> 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()会更快。
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
>>> h = [] #定义一个list
>>> from heapq import * #引入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
|
1
2
3
4
5
6
7
8
|
>>> h
[ 1 , 2 , 9 , 5 ]
>>> heappop(h)
1
>>> heappushpop(h, 4 ) #增加4同时删除最小值2并返回该最小值,与下列操作等同:
2 #heappush(h,4),heappop(h)
>>> h
[ 4 , 5 , 9 ]
|
1
2
3
4
5
6
7
8
9
10
|
>>> a = [ 3 , 6 , 1 ]
>>> heapify(a) #将a变成堆之后,可以对其操作
>>> heappop(a)
1
>>> b = [ 4 , 2 , 5 ] #b不是堆,如果对其进行操作,显示结果如下
>>> heappop(b) #按照顺序,删除第一个数值并返回,不会从中挑选出最小的
4
>>> heapify(b) #变成堆之后,再操作
>>> heappop(b)
2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
>>> a = []
>>> heapreplace(a, 3 ) #如果list空,则报错
Traceback (most recent call last):
File "<stdin>" , line 1 , in <module>
IndexError: index out of range
>>> 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 ]
|
1
2
3
4
5
|
>>> a = [ 2 , 4 , 6 ]
>>> b = [ 1 , 3 , 5 ]
>>> c = merge(a,b)
>>> list (c)
[ 1 , 2 , 3 , 4 , 5 , 6 ]
|
希望本文所述对大家Python程序设计有所帮助。
原文链接:http://www.cnblogs.com/apple2016/p/5744497.html