3

数学関数を実装しており、プライオリティ キューが必要です。このページにあるこのコードを使用します。

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 が遅いことは知られていますが、結果を見ると、dequeue が総実行時間の 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

アップデート：

heapq の使用がほぼ半分に減少

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:

このループを最適化する方法はありますか?

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

2 に答える 2

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 に答える