我正在實現數學函數，因此需要有一個優先級隊列。我使用此頁上的以下代碼：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
2 回答
慕尼黑的夜晚無繁華
TA貢獻1864條經驗 獲得超6個贊
您可以使用該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]}
動漫人物
TA貢獻1815條經驗 獲得超10個贊
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)
添加回答
舉報
0/150
提交
取消