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 heap

heappush(heap, item) # pushes a new item on the heap

item = heappop(heap) # pops the smallest item from the heap

item = heap[0]       # smallest item on the heap without popping it

heapify(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:

    estimated += self.items[k].value

    totalSize += self.items[k].weight

    k += 1  

==  

estimated = sum(item.value for item in self.items)

totalSize = sum(item.weight for item in self.items)