Python：优先级队列不对相同优先级元素保持顺序

Question

我正在使用python的Queue.PriorityQueue，并遇到以下问题：当将几个具有相同优先级的元素插入队列时，我希望队列按插入顺序（FIFO）为它们提供服务。由于某些原因，情况并非如此：

>>> from Queue import PriorityQueue
>>>
>>> j1 = (1, 'job1')
>>> j2 = (1, 'job2')
>>> j3 = (1, 'job3')
>>> j4 = (1, 'job4')
>>> 
>>> q = PriorityQueue()
>>> q.put(j1)
>>> q.put(j2)
>>> q.put(j3)
>>> q.put(j4)
>>> q.queue
[(1, 'job1'), (1, 'job2'), (1, 'job3'), (1, 'job4')]
>>> q.get()
(1, 'job1')
>>> q.queue
[(1, 'job2'), (1, 'job4'), (1, 'job3')]

从示例中可以看出，顺序是1之后混合的get()。什么原因？如何克服（保持相同的Prio元素的顺序）？

编辑：

我被要求添加一个示例，该示例显示q.get()实际上弄乱了FIFO的顺序，因此这是一个精心制作的示例：

class Job(object):
    def __init__(self, type_, **data):
        self.type_ = type_
        self.priority = 0 if self.type_ == 'QUIT' else 1
        self.data = data

    def __cmp__(self, other):
        return cmp(self.priority, other.priority)

    def __repr__(self):
        return 'Job("' + self.type_ + '", data=' + repr(self.data) + ')' 

q = PriorityQueue()
q.put(Job('Build'))
q.put(Job('Clean'))
q.put(Job('QUIT'))
q.put(Job('Create'))
q.put(Job('Build'))
q.put(Job('Clean'))

现在，我将逐个出队。预期的结果：QUIT首先退出，然后其余的按FIFO顺序排序：生成，清理，创建，生成，清理：

>>> q.get()
Job("QUIT", data={})
>>> q.get()
Job("Build", data={})
>>> q.get()
Job("Clean", data={})
>>> q.get()
Job("Build", data={}) # <<---
>>> q.get()
Job("Clean", data={})
>>> q.get()
Job("Create", data={})

Answer 1

优先级队列“通常使用堆来实现”，Python也不例外。如文档所述，它是“使用heapq模块”。而且堆自然不会提供稳定性。这就是为什么heapsort “不是稳定的排序”的原因。如果需要稳定性，则需要自己实施。幸运的是，它就像存储条目“作为包含优先级，条目计数和任务的3元素列表”一样简单。

请注意，您为Python的优先级队列分配了优先级和任务对，但是该队列并不在乎。它没有将两个值视为优先级和任务。它只是将这对视为一个 “项目”，甚至从来没有考虑过。只有我们用户认为这对是优先任务。因此，您也可以单独给它分配任务字符串，而无需额外的优先级。队列甚至没有注意到。它不会尝试提取某些优先级。对于其优先级，它只是询问整个项目是否小于另一个项目。这就是为什么当您不仅要按任务的自然顺序（例如，字符串'job1'小于string 'job2'）对任务进行优先级排序时，会使用优先级和任务元组。元组按字典顺序排序，(a, b)小于(c, d)if a小于c或等于或b小于d。因此，当队列询问这样的元组是否小于另一个元组时，是元组在自身中查找并首先考虑优先级，然后才可能考虑任务。

另外，q.queue您还要检查队列的基础数据结构。你不应该在乎。不知道为什么它甚至可以访问。但是，如果您检查它，则需要将其视为堆，而不是将其视为排序列表。并非您所说的“订单已混在一起”，而是您误解了该列表。无论如何……您应该关心的顺序实际上是您得到的顺序。用q.get()。如果仅使用来获得该示例的所有四个项目q.get()，您会发现它确实按照插入顺序将它们提供给您。尽管那是因为您要按已排序的顺序插入它们，并且它们只有一种可能的顺序，因为没有相等的项。您'(1, 'job1')因为它是首先插入的，但是因为它是四个元组中最小的（因为优先级相同，并且'job1'是四个字符串中的最小）。而且您会获得(1, 'job2')第二个不是因为它被插入第二个而是因为它是第二个最小的项目。等等。如果您在任何其他顺序插入它们，你仍然会得到他们为了(1, 'job1')，(1, 'job2')，(1, 'job3')，(1, 'job4')。

关于您添加的示例：您的Job对象仅按优先级进行比较。那些Build，Clean，Create，Build和Clean对象均具有相同的优先级。因此，只要队列可以告诉他们，它们都是平等的！这与第一个示例不同，在第一个示例中，四个元组仅允许一个可能的顺序。因此，我们回到了我刚开始所说的那样，堆自然不能提供稳定性，如果您想获得稳定性，则应添加一个条目计数。查看我链接到那里的说明和食谱。它使用列表作为堆并使用heapq函数，但是您可以轻松地使其适应使用a PriorityQueue。尽管可以用那些单独的顶级帮助器函数代替它们，但最好将自己的StablePriorityQueue 类定义为的子类或包装器PriorityQueue。