CODEWITHSUNDEEP
pythonalgorithmtiming
CalC
CalC

Reputation: 13

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

In the case where python executes more operations, it is slower.

The following is a very simple comparison of two separate nested loops (for finding a Pythagorean triple (a,b,c) which sum to 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()

I expected solution A to shave a second or two off of solution B but instead it increased the time it took to complete. by two seconds.

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

It seems to me that solution a should vastly improve speed by cutting out thousands to millions of operations, but it in fact does not.

I am aware that there is a simple way to vastly improve this algorithm but I am trying to understand why python would run slower in the case that would seem to be faster.

Upvotes: 1

Views: 66

Answers (3)

smci
smci

Reputation: 33950

Yes there is a performance difference, but because your code is doing different things:

  • Solution A runs c over the range(1000-(a+b), 1000), which will be much shorter. (in fact it doesn't need to run c, it only needs to check for one value c = 1000-(a+b), since that's the only c-value for given a,b that satisfies the constraint (a + b + c) == 1000))
    • however it does compute and store ab = 1000-(a+b), which will be stored in the locals() dict
  • Solution B runs c over the entire range(b, 1000). But it just uses the expression 1000-(a+b) directly, it doesn't store it to a local variable ab.

Upvotes: -1

Prune
Prune

Reputation: 77857

You have two false premises in your confusion:

  • The methods find all triples. They do not; each one finds a single triple and then aborts.
  • The upper method (aka "solution A") does fewer comparisons.

I added some basic instrumentation to test your premises:

import time

#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

Output:

200 375 425
115425626 37.674554109573364
200 375 425
81137726 25.986871480941772

Solution B considers fewer triples. Do the math ... which is the lower value, b or 1000-a-b for this exercise?

Upvotes: 1

sanyassh
sanyassh

Reputation: 8520

You can just count total amount of iterations in each solution and see that A takes more iterations to find the result:

#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()

Output:

A: 115425626
B: 81137726

That's why A is slower. Also ab = 1000 - (a + b) takes time.

Upvotes: 2

Related Questions