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

Python cookbook（數(shù)據(jù)結(jié)構(gòu)與算法）實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法示例

 更新時(shí)間：2018年02月18日 08:13:33   作者：壟上行  
這篇文章主要介紹了Python cookbook（數(shù)據(jù)結(jié)構(gòu)與算法）實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法,結(jié)合實(shí)例形式分析了Python中基于給定優(yōu)先級(jí)進(jìn)行隊(duì)列元素排序的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法。分享給大家供大家參考，具體如下：

問(wèn)題：要實(shí)現(xiàn)一個(gè)隊(duì)列，它能夠以給定的優(yōu)先級(jí)對(duì)元素排序，且每次pop操作時(shí)都會(huì)返回優(yōu)先級(jí)最高的那個(gè)元素；

解決方案：采用heapq模塊實(shí)現(xiàn)一個(gè)簡(jiǎn)單的優(yōu)先級(jí)隊(duì)列

# example.py
#
# Example of a priority queue
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]
# Example use
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)
print("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())


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 ================================
>>> 
Should be bar: Item('bar')
Should be spam: Item('spam')
Should be foo: Item('foo')
Should be grok: Item('grok')
>>>

可以看出：第一次執(zhí)行pop()操作時(shí)返回的元素具有最高的優(yōu)先級(jí)；對(duì)于相同優(yōu)先級(jí)的兩個(gè)元素（foo和gork）返回的順序同它們插入到隊(duì)列時(shí)的順序相同。

在這段代碼中，隊(duì)列以元組(-priority, self._index, item)的形式組成，priority取負(fù)值是為了隊(duì)列按照從高到低的順序排列，這和堆默認(rèn)的從小到大的排序相反。

變量index的作用是對(duì)相同優(yōu)先級(jí)的元素以適當(dāng)?shù)捻樞蚺帕?，特別對(duì)同優(yōu)先級(jí)的元素間做比較操作時(shí)扮演了重要的角色。

Item實(shí)例無(wú)法進(jìn)行次序比較：

a=Item('foo')
b=Item('bar')
print('a<b: ',a<b)
>>> 
Traceback (most recent call last):
 File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 27, in <module>
  print('a<b: ',a<b)
TypeError: unorderable types: Item() < Item()
>>>

如果以元組(priority,  item)的形式來(lái)表示元素，只要優(yōu)先級(jí)不同，就可進(jìn)行比較：

a=(1,Item('foo'))
b=(5,Item('bar'))
c=(1,Item('gork'))
print('a<b: ',a<b)
print('a<c: ',a<c)
>>> 
a<b: True
Traceback (most recent call last):
 File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 29, in <module>
  print('a<c: ',a<c)
TypeError: unorderable types: Item() < Item()
>>>

引入額外的索引值，以(priority, index, item)的方式建立元組，就可以避免相同優(yōu)先級(jí)無(wú)法比較的問(wèn)題，因?yàn)闆](méi)有哪兩個(gè)元組會(huì)有相同的index值；

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

如果想將這個(gè)隊(duì)列用于線程間通信，還需要增加適當(dāng)?shù)逆i和信號(hào)機(jī)制。

（代碼摘自《Python Cookbook》）

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

相關(guān)文章

最新評(píng)論