3

I'm implementing a mathematical function, and I need to have a priority queue. I use this code found on this page:

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

It is known that python is slow, but seeing the results I realized that the dequeue consumes 28% of total execution time. Anyone got any suggestions?

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

UPDATE:

Using heapq decreased almost half

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    67                                               @profile
    68                                               def solution(self):
    69                                           
    70         1           13     13.0      0.0          root = Node(0, 0, 0)
    71         1            2      2.0      0.0          root.capacity = self.K - root.size
    72         1           70     70.0      0.0          root.estimated = self.bound(root.level, root.size, root.value)
    73         1            5      5.0      0.0          root.copyList(None)
    74         1            5      5.0      0.0          heappush(self.queue, (-0, root))
    75                                           
    76     99439       171957      1.7      1.5          while self.queue:
    77                                           
    78     99438      2488221     25.0     21.7              node = heappop(self.queue)[1]
    79                                           
    80     99438       227451      2.3      2.0              if node.estimated > self.maxValue:

Is there any way to optimize this loop?

 while k < self.numItems:
            estimated += self.items[k].value
            totalSize += self.items[k].weight
            k += 1
4

2 回答 2

6

You can use the heapq module.

As long as you do not use multithreading, it can do what you want and may be faster than other priority queues.

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

Here is an example: 

>>> 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) can be used to determine the number of elements inside.

The loop you mentioned should look like this when l has only integers:

l = [(3, 1000), (4, 2000), (5, 500)]
estimated = sum(t[1] for t in l)
totalSize = sum(t[0] for t in l)

Alternatives

If you have a small number of priorities and a large number of elements then buckets would be good. {priority : [queue]}

于 2013-06-26T19:35:40.230 回答
1 
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)
于 2013-06-26T20:43:38.547 回答