python - 基于时间的算法中的优化

Question

我正在为这个问题写一个算法，算法很简单，我已经写了代码但是我看不到任何可能的优化:

I have a bucket with 100 stones and 5 children that use it for decorate their sand castles. Every child pick up a stone repeatedly every a certain span of time, every child is independent from the others, more children can pick up a stone in the same time, there are 5 children in totals:

• Eric pick up a stone every 5 minutes
• Mark pick up a stone every 10 minutes
• Lara pick up a stone every 7 minutes
• Emma pick up a stone every 3 minutes
• Frank pick up a stone every 3 minutes

How many minutes exactly we need for empty the bucket?

To be more clear: after 10 minutes, Erick has up two stones (minute 5 and minute 10), while Emma has 3 stones (minute 3, 6 and 9).

So after 10 minutes the children have 2 + 1 + 1 + 3 + 3 = 10 stones in total, there are 90 stones in the bucket

这是我的代码(Python 3):

children_rate = [3, 3, 5, 7, 10]
bucket = 100

minutes = 0

while True:
    minutes += 1
    for child in children_rate:
        if minutes % child == 0:
            bucket -= 1
            if bucket == 0:
                print('bucket empty in',minutes,'minutes')
                exit()

此代码有效，在本例中所需的分钟数为 91，但我无法使用此代码处理包含 100 万 block 石头和 500 个 child 的桶。

我能看到的唯一优化是将 mod 运算转换为求和/加运算，因为除法/乘法的成本更高。我可以使用 numpy 数组等等，但没有什么能真正加快这个过程。

我曾尝试使问题适应我的算法教科书中描述的一些典型的已知问题，但运气不佳。

Answer 1

您可以翻转算法，以便在给定的分钟数内计算出所有 child 使用了多少石头。

def compute_stones(minutes)
    stones = 0
    for child in children_rate:
        stones += minutes // child  # integer division
    return stones

然后你可以做一个二分法来找到 stones = 100 的分钟数