欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實(shí)現(xiàn)優(yōu)先級隊(duì)列結(jié)構(gòu)的方法詳解

 更新時(shí)間:2016年06月02日 14:59:16   作者:mattkang  
優(yōu)先級隊(duì)列(priority queue)是0個(gè)或多個(gè)元素的集合,每個(gè)元素都有一個(gè)優(yōu)先權(quán),接下來就來看一下簡潔的Python實(shí)現(xiàn)優(yōu)先級隊(duì)列結(jié)構(gòu)的方法詳解:

最簡單的實(shí)現(xiàn)
一個(gè)隊(duì)列至少滿足2個(gè)方法,put和get.
借助最小堆來實(shí)現(xiàn).
這里按"值越大優(yōu)先級越高"的順序.

#coding=utf-8 
from heapq import heappush, heappop 
class PriorityQueue: 
  def __init__(self): 
    self._queue = [] 
 
  def put(self, item, priority): 
    heappush(self._queue, (-priority, item)) 
 
  def get(self): 
    return heappop(self._queue)[-1] 
 
q = PriorityQueue() 
q.put('world', 1) 
q.put('hello', 2) 
print q.get() 
print q.get() 

使用heapq模塊來實(shí)現(xiàn)
下面的類利用 heapq 模塊實(shí)現(xiàn)了一個(gè)簡單的優(yōu)先級隊(duì)列:

import heapq

class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0

  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item))
    self._index += 1

  def pop(self):
    return heapq.heappop(self._queue)[-1]

下面是它的使用方式:

>>> class Item:
...   def __init__(self, name):
...     self.name = name
...   def __repr__(self):
...     return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

仔細(xì)觀察可以發(fā)現(xiàn),第一個(gè) pop() 操作返回優(yōu)先級最高的元素。 另外注意到如果兩個(gè)有著相同優(yōu)先級的元素( foo 和 grok ),pop操作按照它們被插入到隊(duì)列的順序返回的。

 函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素, 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(1.4節(jié)已經(jīng)討論過這個(gè)問題)。 heappop() 函數(shù)總是返回”最小的”的元素,這就是保證隊(duì)列pop操作返回正確元素的關(guān)鍵。 另外,由于push和pop操作時(shí)間復(fù)雜度為O(log N),其中N是堆的大小,因此就算是N很大的時(shí)候它們運(yùn)行速度也依舊很快。

在上面代碼中,隊(duì)列包含了一個(gè) (-priority, index, item) 的元組。 優(yōu)先級為負(fù)數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個(gè)跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。

index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個(gè)不斷增加的 index 下標(biāo)變量,可以確保元素按照它們插入的順序排序。 而且, index 變量也在相同優(yōu)先級元素比較的時(shí)候起到重要作用。

為了闡明這些,先假定Item實(shí)例是不支持排序的:

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

如果你使用元組 (priority, item) ,只要兩個(gè)元素的優(yōu)先級不同就能比較。 但是如果兩個(gè)元素優(yōu)先級一樣的話,那么比較操作就會跟之前一樣出錯(cuò):

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

通過引入另外的 index 變量組成三元組 (priority, index, item) ,就能很好的避免上面的錯(cuò)誤, 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候,如果前面的比較以及可以確定結(jié)果了, 后面的比較操作就不會發(fā)生了:

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>

如果你想在多個(gè)線程中使用同一個(gè)隊(duì)列,那么你需要增加適當(dāng)?shù)逆i和信號量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。

深入思考
函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素, 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(1.4節(jié)已經(jīng)討論過這個(gè)問題)。 heappop() 函數(shù)總是返回”最小的”的元素,這就是保證隊(duì)列pop操作返回正確元素的關(guān)鍵。 另外,由于push和pop操作時(shí)間復(fù)雜度為O(log N),其中N是堆的大小,因此就算是N很大的時(shí)候它們運(yùn)行速度也依舊很快。

在上面代碼中,隊(duì)列包含了一個(gè) (-priority, index, item) 的元組。 優(yōu)先級為負(fù)數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個(gè)跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。

index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個(gè)不斷增加的 index 下標(biāo)變量,可以確保元素按照它們插入的順序排序。 而且, index 變量也在相同優(yōu)先級元素比較的時(shí)候起到重要作用。

為了闡明這些,先假定Item實(shí)例是不支持排序的:

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

如果你使用元組 (priority, item) ,只要兩個(gè)元素的優(yōu)先級不同就能比較。 但是如果兩個(gè)元素優(yōu)先級一樣的話,那么比較操作就會跟之前一樣出錯(cuò):

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

通過引入另外的 index 變量組成三元組 (priority, index, item) ,就能很好的避免上面的錯(cuò)誤, 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候,如果前面的比較以及可以確定結(jié)果了, 后面的比較操作就不會發(fā)生了:

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>

如果你想在多個(gè)線程中使用同一個(gè)隊(duì)列,那么你需要增加適當(dāng)?shù)逆i和信號量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。

heapq 模塊的官方文檔有更詳細(xì)的例子程序以及對于堆理論及其實(shí)現(xiàn)的詳細(xì)說明。

相關(guān)文章

  • Python基于回溯法子集樹模板解決馬踏棋盤問題示例

    Python基于回溯法子集樹模板解決馬踏棋盤問題示例

    這篇文章主要介紹了Python基于回溯法子集樹模板解決馬踏棋盤問題,簡單描述了國際象棋馬踏棋盤問題,并結(jié)合實(shí)例形式分析了Python使用回溯法子集樹模板解決馬踏棋盤問題的具體步驟與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下
    2017-09-09
  • 對Python中的條件判斷、循環(huán)以及循環(huán)的終止方法詳解

    對Python中的條件判斷、循環(huán)以及循環(huán)的終止方法詳解

    今天小編就為大家分享一篇對Python中的條件判斷、循環(huán)以及循環(huán)的終止方法詳解,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-02-02
  • 詳解Python中的上下文管理器原理

    詳解Python中的上下文管理器原理

    這篇文章主要為大家詳細(xì)介紹了Python中的上下文管理器的原理與使用,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-03-03
  • Python幫你解決手機(jī)qq微信內(nèi)存占用太多問題

    Python幫你解決手機(jī)qq微信內(nèi)存占用太多問題

    你有沒有發(fā)現(xiàn)以前16G內(nèi)存也可以裝幾個(gè)游戲玩,現(xiàn)在128G的卻日常使用都不夠了?更不用說裝什么游戲,這其實(shí)是軟件內(nèi)存占用過多導(dǎo)致的,今天我們用python來清理下
    2022-02-02
  • 使用Python制作獲取網(wǎng)站目錄的圖形化程序

    使用Python制作獲取網(wǎng)站目錄的圖形化程序

    這篇文章主要介紹了使用Python制作獲取網(wǎng)站目錄的圖形化程序,GUI制作使用到了PyQt,需要的朋友可以參考下
    2015-05-05
  • python 布爾操作實(shí)現(xiàn)代碼

    python 布爾操作實(shí)現(xiàn)代碼

    python布爾操作也是我們經(jīng)常寫代碼需要用到的,首先我們需要明白在python里面,哪些被解釋器當(dāng)做真,哪些當(dāng)做假
    2013-03-03
  • python求平均值多種方法代碼示例

    python求平均值多種方法代碼示例

    要求一個(gè)列表中的數(shù)的平均值,我們可以使用Python來實(shí)現(xiàn),這篇文章主要給大家介紹了關(guān)于python求平均值多種方法的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-11-11
  • Django ORM 自定義 char 類型字段解析

    Django ORM 自定義 char 類型字段解析

    這篇文章主要介紹了Django ORM 自定義 char 類型字段解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-08-08
  • Python文件路徑名的操作方法

    Python文件路徑名的操作方法

    對于文件路徑名的操作在編程中是必不可少的,比如說,有時(shí)候要列舉一個(gè)路徑下的文件,那么首先就要獲取一個(gè)路徑,再就是路徑名的一個(gè)拼接問題,通過字符串的拼接就可以得到一個(gè)路徑名。這篇文章主要介紹了Python中文件路徑名的操作,需要的朋友可以參考下
    2019-10-10
  • python 通過類中一個(gè)方法獲取另一個(gè)方法變量的實(shí)例

    python 通過類中一個(gè)方法獲取另一個(gè)方法變量的實(shí)例

    今天小編就為大家分享一篇python 通過類中一個(gè)方法獲取另一個(gè)方法變量的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-01-01

最新評論