"For y in range(1,x)"循环运行时间过长。如何在Python中加快这个过程？

Question

此代码需要 40 秒才能以 1000 的顺序运行。我需要在订单 = 100,000,000 时运行它。有没有办法让我加快这段代码？

from fractions import Fraction
x=5
order=1000
count=0
while x <=order:
for y in range(1,x):
if str(Fraction(y/x).limit_denominator()) != "%s/%s"%(y,x):
print(Fraction(y/x).limit_denominator())
count += 1
print(" ")
x+=1
count= (count + 1) * 6 + (order -1)*6
print(count)

此代码的目的是破译欧拉项目上的问题 #351。我对Python的理解有限，所以我试图用我所知道的来弄清楚它。我最初认为每行隐藏的绿点都很容易找到((n-1)* 6)，但确定中心点是一个更大的挑战。发现每个受阻绿点的图案不是线性的，而是将六个三角形中每个三角形的行视为分数的问题，并找到简化的分数。此代码分析三角形的每个"行"以查找简化的分数。如果找到一个，代码将变量"count"加 1。由于 while 循环从第 5 行开始(第一个绿点之外 1 行)，我不得不将这些点添加回末尾的最终计数 ((count + 1)* 6)。我使用此代码来确认以 1000 的顺序找到的绿点。不过花了 40 秒才运行。100,000,000 可能需要更长的时间(几天到几周以上)。截至美国东部标准时间2018年1月11日晚上11：34，我已经在计算机上运行了一天半以上。

Answer 1

正如其他人所提到的，你的算法很复杂，但你也用错了Fraction。使用双参数版本，绝对不要转换和比较字符串。你也在建造和调用Fraction(y/x).limit_denominator()两次，没有充分的理由。

这将大大加快代码速度，但无助于算法的复杂性：

order = 1000
x = 5
count = 0
while x <= order:
for y in range(1, x):
frac = Fraction(y, x)  # don't use y/x
if frac.numerator != y:
# print(frac)  # if you *must* print, reuse this
count += 1
# print(" ")
x += 1
count = (count + 1) * 6 + (order - 1) * 6
print(count)