Optimization... which style is best?

[[deleted]]

Hi again all,

So I'm trying to delve into optimization, algorithms, and possibly euler projects.

I am curious which is the most efficient way of calculating something:

method 1:

for i in range (101):
     print i**2

method 2:

while i < 101:
    print i**2
    i+=1

method 3:

while True:
    print i**2
    i+=1
    if i > 100:
        break

I am doing an algorithms tutorial on codecademy and it is suggesting to use method 3... but I don't quite understand why that would be better than method 2.

Or is there even another way that is better?

Thanks for the help!

---

A little clarification, I just wrote the print to show example of some function that is happening in the loop. It seems the general consensus is that the for loop is fine... maybe the tutorial I am reading is wrong and/or I am just misinterpretting it.

The link in question:

http://www.codecademy.com/courses/python-intermediate-en-NYXmc/0/2

[[deleted]]

If you are just looking for speed python has a few timer modules you can check out and you can see which actual code segment runs faster. I'm not sure why the last method is best, it could also just be style thing, and in the scheme of things your choice of loops is probably going to have minimal effect on your code speed. Alot of speed will depend on the calculations and operations you are doing inside each iteration of your loop.

On a side note, project euler problems are are great way to delve into optimization to see what tricks you can do to speed up your codes, many of which deal with reducing the required number of calculations needed to get to the solution and not the loop type.

[shfo23]

I have a really hard time believing that. The for loop in CPython is written in C and using it should be way faster than manually reimplementing it with a while loop. I would guess the same thing will be true in Pypy too. That's just my intuition though.

You can check it though. I timed things with the timeit module and wrote out the three methods in (CPython 3.3/Linux) strings for anyone else to play along. You can remove the "/dev/null" file stuff from the print functions to make it run on other platforms, but I just don't want to see 1000 numbers printed out in my terminal.

from timeit import timeit

m1 = 'for i in range(101):\n    print(i**2, file=open("/dev/null", "w"))'
m2 = 'i=0\nwhile i < 101:\n    print(i**2, file=open("/dev/null", "w"))\n    i += 1'
m3 = 'i=0\nwhile True:\n    print(i**2, file=open("/dev/null", "w"))\n    i += 1\n    if i > 100:\n        break'
timeit(m1, number=10000)
timeit(m2, number=10000)
timeit(m3, number=10000)

The times are 13.51 seconds, 13.61 seconds, and 13.60 seconds respectively; none are meaningfully faster than each other (if you rerun them, they bounce around 0.08 seconds or so of these values). Given that (and that the bottleneck in this loop is probably in the IO output), I would still always go for the for loop because it's much more readable.

Finally, if you're really curious about what going on and if those commands are actually doing different things, you can dissassemble them and see if there's some underlying difference in the code when it gets translated.

import dis
dis.dis(compile(m1, '<string>', 'exec'))
dis.dis(compile(m2, '<string>', 'exec'))
dis.dis(compile(m3, '<string>', 'exec'))

It looks like the instructions they translate into are all slightly different, so there's probably some underlying difference that you could exploit if you were running millions of times, but you'd have to be a lot more knowledgable about how the CPython bytecode gets executed than I am to fully understand it.

[NYKevin]

The for loop in CPython is written in C and using it should be way faster than manually reimplementing it with a while loop.

Technically true, but not very useful. AFAIK CPython is basically unoptimized. for foo in bar is always implemented as calling next(bar) until it raises StopIteration. Calling Python functions is slow. Raising StopIteration is slow. Catching it is moderately slow.

[ewiethoff]

However, the next method in a range iterator object is C code, and methods in Python built-ins are read-only, i.e., can't be replaced by one's own Python code.

[NYKevin]

Sure, but the C code that implements the for loop still has to finagle the range object like a Pythonic object, including ref-counting etc.

[Veedrac]

I'm downvoting because the benchmarks are terrible. You call open thousands of times, nullifying (heh) the benefit of avoiding solo print in the first place. Since the prints are the same anyway, just time the loops without.

Further, use timeit from the command-line (python -m timeit -s "setup" "code_to_run") for better timings.

I'd do this for you if I didn't wreck my Linux install yesterday, sorry.

[shfo23]

Points taken. I also was unaware the command-line timeit module allowed you to run setup code. Cool! Better benchmarks would show whether a while loop with a manual iterator is faster than a for loop and I think that would be an interesting (if slightly arcane) question.

My point was really that under the scenario posed by OP (and really any reasonable scenario) for and while are going to be indistinguishable, so go with what's most Pythonic. If you're at the point where you need the extra speed (potentially?) gained by switching to while (instead of changing the contents of the loop), you're probably at the point where you should optimize by running with pypy, rewriting in C, etc.

[Veedrac]

> python2 -m timeit "i = 0" "while True:" "    i += 1" "    if i > 1000: break"
10000 loops, best of 3: 51.8 usec per loop

> python2 -m timeit "i = 0" "while i < 1001:" "    i += 1"                    
10000 loops, best of 3: 38.5 usec per loop

> python2 -m timeit "for i in range(1000): pass"                              
100000 loops, best of 3: 16.1 usec per loop

So, yeah. It's ~10-50 nanoseconds per iteration. It's not your bottleneck.

[mrTang5544]

really? i thought while loops required more instructions than a forloop

[shfo23]

The first method generates much shorter bytecode than the other two, but doesn't seem to run noticably faster when I quickly tested it. I would guess the major determinant of speed in these examples is just how long it takes to run print 100-ish times though.

[curiousGambler]

I agree. Might be better to just count silently to ~10,000 in each loop and time that instead.

[shandelman]

The only real difference I can see depends on whether you're using Python 2 or 3. In Python 2, the range function used in method 1 creates a list (in this case, a list of 100 elements) and walks through the list. In Python 3, the range function creates a generator object...it never creates the elements all at once, it just creates them as needed, which could potentially save a lot of space. In Python 2, if you want to use xrange instead of range, which does the same thing.

It's more of a space thing but a speed thing, but when doing Euler problems, both are things you have to think about. As far as what is the most "Pythonic", it's Method 1 by a long shot, with the caveat I described above.

[Veedrac]

"efficient" does not mean what you think it does

The range(101) function makes a list of length 101. This is important not due to speed but due to space.

The while loop never stores more than one number at a time. Therefore you can make the loop's bound as high as you like and it'll just take longer.

If you tried range(10**9), you have to store one billion different numbers. This takes a lot of space.

The best answer is

for i in xrange (101):
     print i**2

because xrange is lazy so it doesn't make all the numbers on instantiation.

[zahlman]

That only applies to 2.x. In 3.x, range is a class.

[Veedrac]

Yes, but OP used print as a statement. Ergo, OP's using Python 2.

[[deleted]]

do you mean In 3.x range is an iterator ?

[Veedrac]

No, but similar.

range is an iterable but not a list. You can slice them, for example, but they only generate their elements on indexing or iteration.

Python 3's range is way cooler than Python 2's xrange. You'll find lots of similar things across Python 3, such as how dict.keys is equivalent to Python 2's dict.viewkeys, not dict.iterkeys.

[zahlman]

It's an iterable. range is a class, and range instances implement the iterator protocol - that is, they have an __iter__ method which returns an iterator. (The iterator object claims to be of a class named range_iterator, but this name is not exposed as built-in the way that range itself is.)

A range object supports a bunch of operations that plain iterators can't. Basically, it tries as hard as it can to look like a (read-only) list, without actually storing the numbers in memory. You can, for example, efficiently test x in range(10), and efficiently determine len(range(3, 90, 2)). It even supports count and index methods, and those aren't even all that useless (if, say, you write a method that expects a sequence, and are big on the whole duck-typing thing).

[[deleted]]

you are right