Python:for循环耗时太长

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (1401)

我正在尝试编写一个代码来解决在线看到的减少分数问题。对于n和d的小值,我得到一个答案,但是当试图求解n和d的大值时,for循环需要很长时间才能得到内存错误(在等待代码运行大约一个小时之后) )。

“通过按大小的升序列出d≤1,000,000的减少的适当分数集......”

有没有办法可以在不使用冗长的for循环的情况下检查n的大值的所有可能分数?

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])
提问于
用户回答回答于

我想可能有比我在这里提出的方法更有效的方法,但是当你意识到你不需要计算分子和分母在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))

这输出:

在2/7 = 0.2857142857142857左边的分数是285713/99996 = 0.28571414285657143

请注意,引用提及d≤1,000,000,因此您需要range(1000001)包含该限制。

扫码关注云+社区

领取腾讯云代金券