PriorityQueue est très lent

Question

J'implémente une fonction mathématique, et j'ai besoin d'une file d'attente prioritaire. J'utilise ce code trouvé sur cette 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

Il est connu que python est lent, mais en voyant les résultats, j'ai réalisé que la dequeue consomme 28% du temps d'exécution total. Quelqu'un a une suggestion à faire ?

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 :

L'utilisation de heapq a diminué de presque la moitié

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:

Y a-t-il un moyen d'optimiser cette boucle ?

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

Answer 1

Vous pouvez utiliser le heapq module.

Tant que vous n'utilisez pas le multithreading, elle peut faire ce que vous voulez et peut être plus rapide que d'autres files d'attente prioritaires.

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

Voici un exemple :

>>> 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) peut être utilisé pour déterminer le nombre d'éléments à l'intérieur.

La boucle que vous avez mentionnée devrait ressembler à ceci lorsque l n'a que des entiers :

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

Alternatives

Si vous disposez d'un petit nombre de priorités et d'un grand nombre d'éléments, les seaux sont une bonne solution. {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)