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

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

这些方法找到了所有的三元组。他们不;每个找到一个三元组然后中止。
上层方法（又名 "solution 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 运行s c 在 range(1000-(a+b), 1000) 之上，这将更短。（实际上它不需要运行 c，它只需要检查一个值 c = 1000-(a+b)，因为对于给定的 a、b 来说，这是唯一满足约束 (a + b + c) == 1000))
- 但是它计算和存储 ab = 1000-(a+b)，它将存储在 locals() dict
解决方案 B 运行s c 在整个 range(b, 1000) 上。但它只是直接使用表达式1000-(a+b)，并没有将其存储到局部变量ab.

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

Python nested-loop speed comparison unexpectedly slower when computing intermediate expression

python

algorithm

timing