Сравнение скорости вложенного цикла Python неожиданно медленнее при вычислении промежуточного выражения

Question

В случае, когда python выполняет больше операций, он работает медленнее.

Ниже приведено очень простое сравнение двух отдельных вложенных циклов (для нахождения пифагорейской тройки (a,b,c), которая в сумме равна 1000):

#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

У вас есть две ложные предпосылки в вашей растерянности:

• Методы находят все тройки. Они не; каждый находит одну тройку, а затем прерывается.
• Верхний метод (он же «решение А») делает меньше сравнений.

Я добавил некоторые базовые инструменты для проверки ваших помещений:

время импорта

#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 запускает c над range(1000-(a+b), 1000), что будет намного короче.(на самом деле ему не нужно запускать c, нужно только проверить одно значение c = 1000-(a+b), поскольку это единственное значение c для заданного a, b, которое удовлетворяет ограничению (a + b + c) == 1000))
  • однако он вычисляет и сохраняет ab = 1000-(a+b), который будет сохранен в locals() dict
• Решение B выполняется c на всем протяжении range(b, 1000).Но он просто использует выражение 1000-(a+b) напрямую, он не сохраняет его в локальной переменной ab.