基于时间的算法中的优化

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 万块石头和 500 个 children 的桶。

我能看到的唯一优化是将 mod 操作转换为 sum/add 操作，因为 division/multiplications 更昂贵。我可以使用 numpy 数组等等，但没有什么能真正加快这个过程。

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

Answer 1

您可以翻转算法，以便在给定的分钟数内计算所有 children.

使用了多少石头

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

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

Answer 2

您可以做的一件事是对答案进行二进制搜索。

假设答案是 X 分钟。然后你就知道在这段时间内每个 child 需要多少石头了。如果取出的石子总数低于预期，X 需要更高。否则，在下半部分搜索。

在代码中：

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

lo, hi = 0, bucket * max (children_rate)
while lo < hi:
    me = (lo + hi) // 2
    if sum (me // i for i in children_rate) < bucket:
        lo = me + 1
    else:
        hi = me

print (lo)

Answer 3

每人child按一定周期取石子，所有child人一起按某种有周期的图案取石子。此模式的周期是每个 child 周期的 Least common multiple。它可以通过多种方式计算，但在这种情况下让我们使用每个周期的因式分解。

3  =   3
5  =     5
7  =       7
10 = 2 * 5

所以常见的时期是210 = 2 * 3 * 5 * 7。这一次埃里克挑选了 42 颗宝石，马克挑选了 21 颗宝石，劳拉挑选了 30 颗宝石，艾玛和弗兰克各挑选了 70 颗宝石。每 210 分钟 233 石。如果你的桶里有 100 万块石头，他们会在 901110 分钟内挑选 999803 块石头，你将运行剩下的 197 块石头的原始代码。很简单，不是吗？

基于时间的算法中的优化

Optimization in a time based algorithm

python

algorithm

optimization

time-complexity