如何将项目放入优先队列？

Question

在Python的文档中，

优先级最低的条目会被最先取出（优先级最低的条目是通过 sorted(list(entries))[0] 返回的）。条目的典型格式是一个元组，形如： (优先级号码, 数据)。

看起来这个队列会先按优先级排序，然后再按数据排序，但这并不总是正确的。比如说，如果“item 2”在“item 1”之前被放入队列，按照优先级，item 1 还是会先被取出。在另一篇文档中，heapq，建议使用一个计数器。所以我会把我的数据存储成 entry = [优先级, 计数, 任务]。这样的话，难道就不需要自己去实现排序了吗？

PriorityQueue.put(item, priority)

Answer 1

我做了一个类似于gfortune的东西，用来实现先进先出（FIFO）的功能，不过不需要到处调用time.time()：这是针对Python 3的。

import time
from dataclasses import dataclass, field

@dataclass(order=True)
class PrioritizedItem:
    prio: int
    timestamp: float = field(init=False, default_factory=time.time)
    data: object = field(compare=False)

现在你可以这样做：

import queue

item1 = PrioritizedItem(0, "hello world")
item2 = PrioritizedItem(0, "what ever")
q = queue.PriorityQueue()
q.put(item1)
q.put(item2)

而且可以放心，它们总是会按照相同的顺序被提取出来。

Answer 2

如果你觉得对字符串数据进行字母数字排序不太合适，可以把元组的第二个元素当作次要优先级来用。比如说，如果你用日期/时间作为优先级，当有多个项目优先级相同的时候，这样的队列就会退回到先进先出的方式。下面是一些示例代码，展示了如何使用一个次要的数字优先级。把日期时间值放在第二个位置其实很简单，如果你遇到问题，随时可以在评论里问我。

代码

import Queue as queue

prio_queue = queue.PriorityQueue()
prio_queue.put((2, 8, 'super blah'))
prio_queue.put((1, 4, 'Some thing'))
prio_queue.put((1, 3, 'This thing would come after Some Thing if we sorted by this text entry'))
prio_queue.put((5, 1, 'blah'))

while not prio_queue.empty():
    item = prio_queue.get()
    print('%s.%s - %s' % item)

输出

1.3 - This thing would come after Some Thing if we didn't add a secondary priority
1.4 - Some thing
2.8 - super blah
5.1 - blah

编辑

如果你用时间戳来模拟先进先出（FIFO）作为次要优先级，效果会是这样的。我说是模拟，因为它并不完全是先进先出，因为如果有多个条目在时间上非常接近，可能不会完全按照先进先出的顺序出来。我加了一个短暂的暂停，这样这个简单的例子就能合理地运行。希望这能帮助你理解如何实现你想要的排序。

import Queue as queue
import time

prio_queue = queue.PriorityQueue()
prio_queue.put((2, time.time(), 'super blah'))
time.sleep(0.1)
prio_queue.put((1, time.time(), 'This thing would come after Some Thing if we sorted by this text entry'))
time.sleep(0.1)
prio_queue.put((1, time.time(), 'Some thing'))
time.sleep(0.1)
prio_queue.put((5, time.time(), 'blah'))

while not prio_queue.empty():
    item = prio_queue.get()
    print('%s.%s - %s' % item)

Answer 3

据我所知，你想要的功能是现成的没有的。不过，值得注意的是，实现起来并不难：

from Queue import PriorityQueue

class MyPriorityQueue(PriorityQueue):
    def __init__(self):
        PriorityQueue.__init__(self)
        self.counter = 0

    def put(self, item, priority):
        PriorityQueue.put(self, (priority, self.counter, item))
        self.counter += 1

    def get(self, *args, **kwargs):
        _, _, item = PriorityQueue.get(self, *args, **kwargs)
        return item


queue = MyPriorityQueue()
queue.put('item2', 1)
queue.put('item1', 1)

print queue.get()
print queue.get()

示例输出：

item2
item1