今天的文章來(lái)介紹Python當(dāng)中一個(gè)蠻有用的庫(kù)——heapq。

heapq的全寫(xiě)是heapqueue，是堆隊(duì)列的意思。這里的堆和隊(duì)列都是數(shù)據(jù)結(jié)構(gòu)，在后序的文章當(dāng)中我們會(huì)詳細(xì)介紹，今天只介紹heapq的用法，如果不了解heap和queue原理的同學(xué)可以忽略，我們并不會(huì)深入太多，會(huì)在之后的文章里詳細(xì)闡述。

在介紹用法之前，我們需要先知道優(yōu)先隊(duì)列的定義。隊(duì)列大家應(yīng)該都不陌生，也是非常基礎(chǔ)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。我們可以想象成隊(duì)列里的所有元素排成一排，新的元素只能從隊(duì)尾加入隊(duì)列，元素要出隊(duì)列只能通過(guò)隊(duì)首，不能中途從隊(duì)列當(dāng)中退出。而優(yōu)先隊(duì)列呢，是給隊(duì)列當(dāng)中的元素每一個(gè)都設(shè)置了優(yōu)先級(jí)，使得隊(duì)伍當(dāng)中的元素會(huì)自動(dòng)按照優(yōu)先級(jí)排序，優(yōu)先級(jí)高的排在前面。

也就是說(shuō)Python當(dāng)中的heapq就是一個(gè)維護(hù)優(yōu)先隊(duì)列的library，我們通過(guò)調(diào)用它可以輕松實(shí)現(xiàn)優(yōu)先隊(duì)列的功能。

最大或最小的K個(gè)元素

我們來(lái)看一個(gè)實(shí)際的問(wèn)題，假設(shè)我們當(dāng)下有N個(gè)雜亂無(wú)章的元素，但是我們只關(guān)心其中最大的K個(gè)或者是最小的K個(gè)元素。我們想從整個(gè)數(shù)組當(dāng)中將這部分抽取出來(lái)，應(yīng)該怎么辦呢?

這個(gè)問(wèn)題在實(shí)際當(dāng)中非常常見(jiàn)，隨便就可以舉出例子來(lái)。比如用戶輸入了搜索詞，我們根據(jù)用戶的搜索詞找到了大量的內(nèi)容。我們想要根據(jù)算法篩選出用戶最有可能點(diǎn)擊的文本來(lái)，機(jī)器學(xué)習(xí)的模型可以給每一個(gè)文本一個(gè)預(yù)測(cè)的分?jǐn)?shù)。之后，我們就需要選出分?jǐn)?shù)最大的K個(gè)結(jié)果。這種類似的場(chǎng)景還有很多，利用heapq庫(kù)里的nlargest和nsmallest接口可以非常方便地做到這點(diǎn)。

我們一起來(lái)看一個(gè)例子：

importheapq

nums=[14,20,5,28,1,21,16,22,17,28]

heapq.nlargest(3,nums)

#[28,28,22]

heapq.nsmallest(3,nums)

#[1,5,14]

heapq的nlargest和nsmallest接受兩個(gè)參數(shù)，第一個(gè)參數(shù)是K，也就是返回的元素的數(shù)量，第二個(gè)參數(shù)是傳入的數(shù)組，heapq返回的正是傳入的數(shù)組當(dāng)中的前K大或者是前K小。

這里有一個(gè)問(wèn)題，如果我們數(shù)組當(dāng)中的元素是一個(gè)對(duì)象呢?應(yīng)該怎么辦?

其實(shí)也很簡(jiǎn)單，有了解過(guò)Python自定義關(guān)鍵詞排序的同學(xué)應(yīng)該知道，和排序一樣，我們可以通過(guò)匿名函數(shù)實(shí)現(xiàn)。

匿名函數(shù)

我們都知道，在Python當(dāng)中通過(guò)def可以定義一個(gè)函數(shù)。通過(guò)def定義的函數(shù)都有函數(shù)名，所以稱為有名函數(shù)。除了有名函數(shù)之外，Python還支持匿名函數(shù)。顧名思義，就是沒(méi)有函數(shù)名的函數(shù)。也就是說(shuō)它其他方面都和普通函數(shù)一樣，只不過(guò)沒(méi)有名字而已。

初學(xué)者可能會(huì)納悶，函數(shù)沒(méi)有名字應(yīng)該怎么調(diào)用呢?

會(huì)有這個(gè)疑惑很正常，這是因?yàn)榱?xí)慣了面向過(guò)程的編程，對(duì)面向?qū)ο罄斫獠粔蛏钊雽?dǎo)致的。在許多高級(jí)語(yǔ)言當(dāng)中，一切皆對(duì)象，一個(gè)類，一個(gè)函數(shù)，一個(gè)int都是對(duì)象。既然函數(shù)也是對(duì)象，那么函數(shù)自然也可以用來(lái)傳遞，不僅可以用來(lái)傳遞，還可以用來(lái)返回。這是函數(shù)式編程的概念了，我們這里不多做深入。

當(dāng)然，普通函數(shù)也一樣可以傳遞，起到的效果一樣。只不過(guò)在編程當(dāng)中，有些函數(shù)我們只會(huì)使用一次，沒(méi)必要再單獨(dú)定義一個(gè)函數(shù)，使用匿名函數(shù)會(huì)非常方便。

舉個(gè)例子，比方說(shuō)我有一個(gè)這樣的函數(shù)：

defoperate(x,func):

returnfunc(x)

這個(gè)operate函數(shù)它接受兩個(gè)參數(shù)，第一個(gè)參數(shù)是變量x，第二個(gè)參數(shù)是一個(gè)函數(shù)。它會(huì)在函數(shù)內(nèi)部調(diào)用func，返回func調(diào)用的結(jié)果。我現(xiàn)在要做這樣一件事情，我希望根據(jù)x這個(gè)整數(shù)對(duì)4取余的余數(shù)來(lái)判斷應(yīng)該用什么樣的func。如果對(duì)4的余數(shù)為0，我希望求一次方，如果余數(shù)是2，我希望求平方，以此類推。如果按照正常的方法，我們需要實(shí)現(xiàn)4個(gè)方法，然后依次傳遞。

這當(dāng)然是可以的，不過(guò)非常麻煩，如果使用匿名函數(shù)，就可以大大簡(jiǎn)化代碼量：

defget_result(x):

ifx%4==0:

returnoperate(x,lambdax:x)

elifx%4==1:

returnoperate(x,lambdax:x**2)

elifx%4==2:

returnoperate(x,lambdax:x**3)

else:

returnoperate(x,lambdax:x**4)

在上面的代碼當(dāng)中，我們通過(guò)lambda關(guān)鍵字定義了匿名函數(shù)，避免了定義四種函數(shù)用來(lái)傳遞的情況。當(dāng)然，這個(gè)問(wèn)題還有更簡(jiǎn)單的寫(xiě)法，可以只用一個(gè)函數(shù)解決。

我們來(lái)看lambda定義匿名函數(shù)的語(yǔ)法，首先是lambda關(guān)鍵字，表示我們當(dāng)下定義的是一個(gè)匿名函數(shù)。之后跟的是這個(gè)匿名函數(shù)的參數(shù)，我們只用到一個(gè)變量x，所以只需要寫(xiě)一個(gè)x。如果我們需要用到多個(gè)參數(shù)，通過(guò)逗號(hào)分隔，當(dāng)然也可以不用參數(shù)。寫(xiě)完參數(shù)之后，我們用冒號(hào)分開(kāi)，冒號(hào)后面寫(xiě)的是返回的結(jié)果。

我們也可以把匿名函數(shù)賦值給一個(gè)變量，之后我們就可以和調(diào)用普通函數(shù)一樣來(lái)調(diào)用了：

square=lambdax:x**2

print(square(3))

print(operate(3,square))

自定義排序

回到之前的內(nèi)容，如果我們想要heapq排序的是一個(gè)對(duì)象。那么heapq并不知道應(yīng)該依據(jù)對(duì)象當(dāng)中的哪個(gè)參數(shù)來(lái)作為排序的衡量標(biāo)準(zhǔn)，所以這個(gè)時(shí)候，需要我們自己定義一個(gè)獲取關(guān)鍵字的函數(shù)，傳遞給heapq，這樣才可以完成排序。

比如說(shuō)，我們現(xiàn)在有一批電腦，我們希望heapq能夠根據(jù)電腦的價(jià)格排序：

laptops=[

{'name':'ThinkPad','amount':100,'price':91.1},

{'name':'Mac','amount':50,'price':543.22},

{'name':'Surface','amount':200,'price':21.09},

{'name':'Alienware','amount':35,'price':31.75},

{'name':'Lenovo','amount':45,'price':16.35},

{'name':'Huawei','amount':75,'price':115.65}

]

cheap=heapq.nsmallest(3,portfolio,key=lambdas:s['price'])

expensive=heapq.nlargest(3,portfolio,key=lambdas:s['price'])

在調(diào)用nlargest和nsmallest的時(shí)候，我們額外傳遞了一個(gè)參數(shù)key，我們傳入的是一個(gè)匿名函數(shù)，它返回的結(jié)果是這個(gè)對(duì)象的price，也就是說(shuō)我們希望heapq根據(jù)對(duì)象的price來(lái)進(jìn)行排序。

優(yōu)先隊(duì)列

heapq除了可以返回最大最小的K個(gè)數(shù)之外，還實(shí)現(xiàn)了優(yōu)先隊(duì)列的接口。我們可以直接調(diào)用heapq.heapify方法，輸入一個(gè)數(shù)組，返回的結(jié)果是根據(jù)這個(gè)數(shù)組生成的堆(等價(jià)于優(yōu)先隊(duì)列)。

當(dāng)然我們也可以從零開(kāi)始，直接通過(guò)調(diào)用heapq的push和pop來(lái)維護(hù)這個(gè)堆。接下來(lái)，我們就通過(guò)heapq來(lái)自己動(dòng)手實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列，代碼非常的簡(jiǎn)單，我想大家應(yīng)該可以瞬間學(xué)會(huì)。

首先是實(shí)現(xiàn)優(yōu)先隊(duì)列的部分：

importheapq

classPriorityQueue:

def__init__(self):

self._queue=[]

self._index=0

defpush(self,item,priority):

#傳入兩個(gè)參數(shù)，一個(gè)是存放元素的數(shù)組，另一個(gè)是要存儲(chǔ)的元素，這里是一個(gè)元組。

#由于heap內(nèi)部默認(rèn)有小到大排，所以對(duì)priority取負(fù)數(shù)

heapq.heappush(self._queue,(-priority,self._index,item))

self._index+=1

defpop(self):

returnheapq.heappop(self._queue)[-1]

其次我們來(lái)實(shí)際看一下運(yùn)用的情況：

q=PriorityQueue()

q.push('lenovo',1)

q.push('Mac',5)

q.push('ThinkPad',2)

q.push('Surface',3)

q.pop()

#Mac

q.pop()

#Surface

到這里，關(guān)于heapq的應(yīng)用方面就算是介紹完了，但是還沒(méi)有真正的結(jié)束。

我們需要分析一下heapq當(dāng)中操作的復(fù)雜度，關(guān)于堆的部分我們暫時(shí)跳過(guò)，我們先來(lái)看nlargest和nsmallest。我在github當(dāng)中找到了這個(gè)庫(kù)的源碼，在方法的注釋上，作者寫(xiě)下了這個(gè)方法的復(fù)雜度，和排序之后取前K個(gè)開(kāi)銷(xiāo)五五開(kāi)：

defnlargest(n,iterable,key=None):

"""Findthenlargestelementsinadataset.

Equivalentto:sorted(iterable,key=key,reverse=True)[:n]

"""

以上內(nèi)容為大家介紹了Python中heapq與優(yōu)先隊(duì)列，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。