PriorityQueue非常慢

Question

我正在实现数学函数，因此需要有一个优先级队列。我使用此页上的以下代码：

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):

        if self.counter == 0:

            return None

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

        self.counter -= 1

        return item

    def empty(self):

        if self.counter == 0:

            return True

        return False

众所周知python速度很慢，但是看到结果我意识到出队消耗了总执行时间的28％。任何人有任何建议吗？

Line #      Hits         Time  Per Hit   % Time  Line Contents

==============================================================

    34                                               @profile

    35                                               def solution(self):

    36                                           

    37         1           11     11.0      0.0          root = Node()

    38         1            2      2.0      0.0          root.capacity = self.K - root.size

    39         1           65     65.0      0.0          root.estimated = self.bound(root.level, root.size, root.value)

    40         1            4      4.0      0.0          root.copyList(None)

    41         1           37     37.0      0.0          self.queue.put(root, -0)

    42                                           

    43     99439       389936      3.9      2.3          while not self.queue.empty():

    44                                           

    45     99438      4666742     46.9     28.0              node = self.queue.get()

    46                                           

    47     99438       272335      2.7      1.6              if node.estimated > self.maxValue:

    48                                           

Answer 1

您可以使用该heapq模块。只要您不使用多线程，它就可以完成您想做的事情，并且可能比其他优先级队列要快。heap = []            # creates an empty heapheappush(heap, item) # pushes a new item on the heapitem = heappop(heap) # pops the smallest item from the heapitem = heap[0]       # smallest item on the heap without popping itheapify(x)           # transforms list into a heap, in-place, in linear time这是一个例子：>>> from heapq import *>>> l = []>>> heappush(l, (4, 'element')) # priority, element>>> l[(4, 'element')]>>> heappush(l, (3, 'element2'))>>> l[(3, 'element2'), (4, 'element')]>>> heappush(l, (5, 'element3'))>>> l[(3, 'element2'), (4, 'element'), (5, 'element3')]>>> heappop(l)(3, 'element2')>>> heappop(l)(4, 'element')>>> heappop(l)(5, 'element3')len(l) 可用于确定内部元素的数量。当l只有整数时，您提到的循环应如下所示：l = [(3, 1000), (4, 2000), (5, 500)]estimated = sum(t[1] for t in l)totalSize = sum(t[0] for t in l)备择方案如果您的优先级较少且元素众多，那么存储桶将是不错的选择。 {priority : [queue]}

Answer 2

while k < self.numItems:&nbsp; &nbsp; estimated += self.items[k].value&nbsp; &nbsp; totalSize += self.items[k].weight&nbsp; &nbsp; k += 1&nbsp;&nbsp;==&nbsp;&nbsp;estimated = sum(item.value for item in self.items)totalSize = sum(item.weight for item in self.items)