Python while loop speed

Question

I would like it if someone could please explain to me why the following code has so much additional overhead. At 100k iterations, the speed is the same for either case (2.2 sec). When increasing to 1E6 iterations case "B" never finishes, while case "A" takes only 29 seconds.

Case "A"

while n is not 1:
    foo

Case "B"

while n > 1:
    foo

Complete code if of any help

def coll(n):
    count = 0
    # while n is not 1:
    while n > 1:
        count += 1
        if not n % 2:
            n /= 2
        else:
            n = 3*n + 1
    return count

for x in range(1,100000):
    count = coll(x)

Both versions with 100,000 iterations run in under 1 second for me. For 1,000,000 iterations, B runs in ~11 seconds, and A is still running. — Cyphase
– Cyphase, Commented Aug 30, 2015 at 1:00
The construction n is not 1 is not in anyway equivalent to n > 1. The first form is not an arithmetic comparison and should not be used. The is not 1 is a statement about object identity and is completely implementation dependent. That is n != 1 is not necessarily equivalent to n is not 1. If you use undefined behavior, your program can do anything it wants, so don't. — msw
– msw, Commented Aug 30, 2015 at 1:06
Sorry, I meant By "A never finishing I mean that I let the program run for 20 minutes without completion so I had to terminate it. I discovered that the IS NOT was causing my script to hang, and have replaced it with !=. — Alan
– Alan, Commented Aug 30, 2015 at 15:52

Cyphase · Accepted Answer · 2015-08-30 01:10:54Z

4

First of all, you should use n > 1 or n != 1, not n is not 1. The fact that the latter works is an implementation detail, and obviously it's not working for you.

The reason it's not working is because there are values of x in your code that cause the Collatz sequence to go over the value of sys.maxint, which turns n into a long. Then, even when it ends up going back down to 1, it's actually 1L; a long, not an int.

Try using while n is not 1 and repr(n) != '1L':, and it'll work as you expect. But don't do that; just use n > 1 or n != 1.

answered Aug 30, 2015 at 1:10

Cyphase

12k3 gold badges33 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Alan Over a year ago

Thank you, for some reason it was in my mind that != was similar to is not. The clarification makes sense as why the code seemed to hang. Is there any reason that n >1 is prefered to n != 1 if both are appropriate for the loop structure?

Cyphase Over a year ago

@Alan, what makes you say that n > 1 is preferred? I would use n != 1, as it seems to make more semantic sense to me, given the properties of the Collatz sequence. Their performance is practically identical in this case.

iobender · Accepted Answer · 2015-08-30 01:02:31Z

2

Generally in Python, is is extremely fast to check, as it uses referential equality, so all that needs to be checked is that two objects have the same memory location. Note that the only reason your code works is that most implementations of Python generally maintain a pool of the smaller integers, so that every 1 always refers to the same 1, for example, where there may be multiple objects representing 1000. In those cases, n is 1000 would fail, where n == 1000 would work. Your code is relying on this integer pool, which is risky.

> involves a function call, which is fairly slow in Python: n > 1 translates to n.__gt__(1).

answered Aug 30, 2015 at 1:02

iobender

3,5461 gold badge21 silver badges21 bronze badges

Collectives™ on Stack Overflow

Python while loop speed

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related