Python 嵌套循环速度比较在计算中间表达式时出乎意料地变慢

Question

在python执行更多操作的情况下，它的速度较慢。

以下是两个独立嵌套循环的非常简单的比较(用于查找总和为 1000 的毕达哥拉斯三重(a,b,c))：

#Takes 9 Seconds
for a in range(1, 1000):
for b in range(a, 1000):
ab = 1000 - (a + b)
for c in range(ab, 1000):
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
exit()

#Solution B
#Takes 7 Seconds
for a in range(1, 1000):
for b in range(a, 1000):
for c in range(b, 1000):
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
exit()

我预计解决方案 A 会从解决方案 B 中减少一两秒钟，但它增加了完成所需的时间。 两秒钟。

instead of iterating
1, 1, 1
1, 1, 2
...
1, 1, 999
1, 2, 2
It would iterate
1, 1, 998
1, 1, 999
1, 2, 997
1, 2, 998
1, 2, 999
1, 3, 996

在我看来，解决方案a应该通过减少数千到数百万次操作来大大提高速度，但实际上并非如此。

我知道有一种简单的方法可以大大改进这种算法，但我试图理解为什么 python 在看起来更快的情况下会运行得更慢。

Answer 1

您可以只计算每个解决方案中的迭代总数，并看到 A 需要更多迭代才能找到结果：

#Takes 9 Seconds
def A():
count = 0
for a in range(1, 1000):
for b in range(a, 1000):
ab = 1000 - (a + b)
for c in range(ab, 1000):
count += 1
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
print('A:', count)
return

#Solution B
#Takes 7 Seconds
def B():
count = 0
for a in range(1, 1000):
for b in range(a, 1000):
for c in range(b, 1000):
count += 1
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
print('B:', count)
return
A()
B()

输出：

A: 115425626
B: 81137726

这就是 A 较慢的原因。ab = 1000 - (a + b)也需要时间。

Answer 2

在你的困惑中有两个错误的前提：

• 这些方法查找所有三元组。 他们没有;每个都找到一个三元组，然后中止。
• 上面的方法(又名"解决方案 A")所做的比较较少。

我添加了一些基本仪器来测试您的前提：

导入时间

#Takes 9 Seconds
count = 0
start = time.time()
for a in range(1, 1000):
for b in range(a, 1000):
ab = 1000 - (a + b)
for c in range(ab, 1000):
count += 1
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
print(count, time.time() - start)
break

#Solution B
#Takes 7 Seconds
count = 0
start = time.time()
for a in range(1, 1000):
for b in range(a, 1000):
for c in range(b, 1000):
count += 1
if(((a + b + c) == 1000) and ((a**2) + (b**2) == (c**2))):
print(a,b,c)
print(count, time.time() - start)
break

输出：

200 375 425
115425626 37.674554109573364
200 375 425
81137726 25.986871480941772

Solution B考虑较少的三元组。 算一算...本练习的b或1000-a-b值较低？

Answer 3

是的，存在性能差异，但因为您的代码正在执行不同的操作：

• 解决方案 A 在range(1000-(a+b), 1000)上运行 c，这会短得多。(实际上它不需要运行 c，它只需要检查一个值c = 1000-(a+b)，因为这是给定 a，b 唯一满足约束(a + b + c) == 1000)的 c 值)
  • 但是它确实计算和存储ab = 1000-(a+b)，这些将存储在locals()字典中
• 解决方案 B 在整个range(b, 1000)上运行 c。但它只是直接使用表达式1000-(a+b)，它不会将其存储到局部变量ab。