Python:for循环花费太长时间

Question

我正在尝试编写一个代码来解决网上看到的约化分数问题。对于较小的 n 和 d 值，我得到了答案，但是当尝试求解较大的 n 和 d 值时，for 循环花费的时间太长，以至于出现内存错误(在等待代码运行大约一个小时后) )。

“通过按大小升序列出 d ≤ 1,000,000 的约化真分数集...”

有没有一种方法可以检查 n 的大值的所有可能分数，而无需使用冗长的 for 循环？

fraction_list = []

for d in range(1000000):
    for n in range(1000000):
        if n<d and n/d ==0 :
            frac = float(n) / float(d)
            #print(frac)
            fraction_list.append(frac)



index_num = (fraction_list.index(float(2.0/7.0)))

sorted(fraction_list, key=float) 
print(fraction_list[index_num])
print("the fraction which is to the left is" + fraction_list[index_num -1])

Answer 1

我想可能有比我在这里介绍的更有效的方法，但当您意识到不需要使用分子和分子来计算所有因子时，至少可以避免双循环分母在 0..1000000 范围内。

您可以只对分母(从 1 开始，而不是 0)执行该循环，然后递增分子(从 0 开始)，直到超出给定的分数。此时将该分子递减一次，因此它代表了潜在的候选解决方案。然后在下一次迭代中——当分母大一时——不需要再次将分子重置为 0，它可以从剩下的地方继续，因为可以肯定新的分数将小于给定的分数:这才是你真正赢得时间的地方。

这意味着您可以使用线性方法而不是二次方法:

def get_prev_fraction(num, denom, limit = 1000000):
    bestnum = 0
    bestdenom = 1
    a = 0
    for b in range(1,limit+1):
        while a*denom < b*num:
            a += 1
        a -= 1
        if a*bestdenom > b*bestnum:
            bestnum, bestdenom = a, b
    return bestnum, bestdenom


num, denom = get_prev_fraction(2, 7)

print("the fraction which is to the left of {}/{}={} is {}/{}={}".format(2, 7, 2.0/7, num, denom, num/denom))

输出:

the fraction which is to the left of 2/7=0.2857142857142857 is 285713/999996=0.28571414285657143

请注意，引用中提到d ≤ 1,000,000，因此您需要执行range(1000001) 来包含该限制。