python - 多个数字连续递减的快速算法，直到和的限制

Question

我有:

• dc 对象的有序列表，其中有一个浮点字段 result。
• limit result 总和的值。
• pack(不是一个更好的名字)是递减的值。

问题:

• 我需要依次减少每个 dc 的 results，直到所有 results 的总和小于或等于 limit(不分配小于 0 的 result 值)。

经过一些分析后，我得到了这段代码:

while(self.sum > self.limit):
    for dc in self.dc:
        if dc.result > 0:
            # max() too slow here
            result = (
                dc.result - self.pack
                if dc.result - self.pack > 0
                else 0
                )
            # Prevent sum() count for all list on each iteration
            self.sum -= dc.result - result
            dc.result = result

            if self.sum <= self.limit:
                break

但是对于较小的 self.pack 值，它的性能较低(代码进行了过多的迭代)。

有没有办法让这个方法更快？

Answer 1

如果您不太关心从包中移除多少，只要它确保它小于总和，那么您可以将 DC 实现为最大堆(优先级队列)，并每次弹出它直到总和为<= self 限制。这将显着加快处理时间，尤其是在大数据集中。

编辑: 由于 dc 是一个有序列表，只需将其视为堆栈并从后面弹出并从包中移除(因为“最重”的东西在后面)。