top - python queue用法




Python的通用優先級隊列 (6)

你看過heapq頁面上的“Show Source”鏈接嗎? 有一個例子,使用一堆(int,char)元組列表作為優先級隊列的一半。

我需要在我的Python代碼中使用優先級隊列。 尋找有效的東西,我來到heapq 。 它看起來不錯,但似乎只對整數指定。 我想它適用於任何具有比較運算符的對象,但是它沒有指定它需要的比較運算符。

另外, heapq好像是用Python實現的,所以不是很快。

你知道Python中的優先級隊列的快速實現嗎? 最好,我想隊列是通用的(即對任何具有指定比較運算符的對像都適用)。

提前致謝

更新:

重新比較heapq ,我可以使用(priority, object)如查理馬丁建議,或者只是實現__cmp__為我的對象。

我仍然在尋找比heapq更快的東西。


嗯, Queue.PriorityQueue ? 回想一下,Python不是強類型的,所以你可以保存任何你喜歡的東西:只要創建一個(優先級,事物)的元組,然後設置。


您可以將heapq用於非整數元素(元組)

from heapq import *

heap = []
data = [(10,"ten"), (3,"three"), (5,"five"), (7,"seven"), (9, "nine"), (2,"two")]
for item in data:
    heappush(heap, item)
sorted = []
while heap:
    sorted.append(heappop(heap))
print sorted
data.sort()
print data == sorted

這是有效的,適用於字符串或任何類型的輸入 - :)

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

參考: http : //docs.python.org/library/heapq.html


我可以使用Charlie Martin建議的(priority, object) ,或者僅僅為我的對象實現__cmp__

如果你希望插入的對象按照一個特定的規則進行優先級排序,我發現寫一個簡單的接受一個按鍵函數的PriorityQueue子類是非常有用的。 您不必手動插入(priority, object)元組,並且處理感覺更自然。

所需行為的演示

>>> h = KeyHeap(sum)
>>> h.put([-1,1])
>>> h.put((-1,-2,-3))
>>> h.put({100})
>>> h.put([1,2,3])
>>> h.get()
(-1, -2, -3)
>>> h.get()
[-1, 1]
>>> h.get()
[1, 2, 3]
>>> h.get()
set([100])
>>> h.empty()
True
>>>
>>> k = KeyHeap(len)
>>> k.put('hello')
>>> k.put('')
>>> k.put('!')
>>> k.get()
'!'
>>> k.get()
'hello'
>>> k.get()
''

Python 2代碼

from Queue import PriorityQueue

class KeyHeap(PriorityQueue):
    def __init__(self, key, maxsize=0):            
        PriorityQueue.__init__(self, maxsize)
        self.key = key

    def put(self, x):
        PriorityQueue.put(self, (self.key(x), x))

    def get(self):
        return PriorityQueue.get(self)[1]

Python 3代碼

from queue import PriorityQueue

class KeyHeap(PriorityQueue):
    def __init__(self, key, maxsize=0):            
        super().__init__(maxsize)
        self.key = key

    def put(self, x):
        super().put((self.key(x), x))

    def get(self):
        return super().get()[1]

很顯然,如果你嘗試插入一個key函數無法處理的對象,那麼調用put會(並且應該)會引發一個錯誤。


我結束了為heapq實現一個包裝,增加了維護隊列的元素唯一的字典。 對於所有運營商來說,結果應該是非常有效的

class PriorityQueueSet(object):

    """
    Combined priority queue and set data structure.

    Acts like a priority queue, except that its items are guaranteed to be
    unique. Provides O(1) membership test, O(log N) insertion and O(log N)
    removal of the smallest item.

    Important: the items of this data structure must be both comparable and
    hashable (i.e. must implement __cmp__ and __hash__). This is true of
    Python's built-in objects, but you should implement those methods if you
    want to use the data structure for custom objects.
    """

    def __init__(self, items=[]):
        """
        Create a new PriorityQueueSet.

        Arguments:
            items (list): An initial item list - it can be unsorted and
                non-unique. The data structure will be created in O(N).
        """
        self.set = dict((item, True) for item in items)
        self.heap = self.set.keys()
        heapq.heapify(self.heap)

    def has_item(self, item):
        """Check if ``item`` exists in the queue."""
        return item in self.set

    def pop_smallest(self):
        """Remove and return the smallest item from the queue."""
        smallest = heapq.heappop(self.heap)
        del self.set[smallest]
        return smallest

    def add(self, item):
        """Add ``item`` to the queue if doesn't already exist."""
        if item not in self.set:
            self.set[item] = True
            heapq.heappush(self.heap, item)




queue