Single Vs. Multiple For Loops In Python?

Question

When comparing the following code samples in python (the 300 is just an example; in practicality, assume there are 10,000,000 items that we need to loop through):

sum = 0
for i in xrange(0, 300):
    sum += i

Vs.

sum = 0
for i in xrange(0, 100):
    sum += i
for i in xrange(100, 200):
    sum += i
for i in xrange(200, 300):
    sum += i

Are both versions the same in terms of running time? I have a problem where I have a huge vector (say, 10,000 items). I don't necessarily have to loop through all of it, unless some conditions are met (these conditions can only be assessed when the first loop -- which using the first 100 items -- is done).

Then, I should continue the looping only if some conditions are met (these conditions can only be assessed when the next 100 items are examined).

Same story, until I reach the end of the vector................

Given the fact that I can solve my problem in a modular way, by examining points:

{0, 100} {100, 200} {200, 300} ........ {9900, 10,000}

All I am trying is to get a sense whether the second approach is as efficient as the first one. Thanks.

note: the sum is used here for simplicity. In practice, the running time of the mathematical operations that will be used is significantly greater. That's why I am trying to find ways to optimize the running time by examining different coding approaches...

By vector, do you mean `list`? Or really a vector, like from C++? — Blender, May 29 '11 at 05:07
@Blender: it is a numpy array. yet, you can assume it is a `list` -- it does not really matter. What I am trying to get a sense is, what is the best coding approach in `python` to solve the problem I am facing. Thanks! — user3262424, May 29 '11 at 05:16

johnsyweb · Accepted Answer · 2011-05-29T06:32:01.050

4

What kind of improvement were you hoping to see?

timeit will help you observe the difference:

$ python -m timeit 'sum = 0
> for i in xrange(0, 300):
>     sum += i'
10000 loops, best of 3: 21.8 usec per loop

$ python -m timeit 'sum = 0
> for i in xrange(0, 100):
>     sum += i
> for i in xrange(100, 200):
>     sum += i
> for i in xrange(200, 300):
>     sum += i'
10000 loops, best of 3: 22.8 usec per loop

Personally, I would go for:

$ python -m timeit 'sum(xrange(300))'
100000 loops, best of 3: 5.34 usec per loop

This example is perhaps not the best way to assess whether you'll be able to optimise your actual code, but it does demonstrate how you can test a small snippet for its running time.

Just remember what Donald Knuth said about optimisation ;-)

Here's a way you could checkpoint your iteration and break out if required:

>>> for index, item in enumerate(vect):
...     results = do_stuff_with(item)
...     if index % 100 == 0 and should_we_stop(results):
...         break

What would be even better is if you could have do_stuff_with() return a tuple indicating whether it has finished, then you can check every iteration whether you're done, rather than wait:

>>> for item in vect:
...     finished, results = do_stuff_with(item)
...     if finished:
...         break

Just to reiterate (no pun intended) it's very hard to say how (or even whether) to optimise your actual code without actually seeing it!

edited May 29 '11 at 06:32

answered May 29 '11 at 05:08

johnsyweb

136,902
23
188
247

Johnsyweb: I edited my post -- please take a look at it to see what I am trying to achieve. Assume that I have a `list` of say 10,000,000 items even. The key is the approach -- if it is sound, or alternatively, better ideas are out there. Thanks. – user3262424 May 29 '11 at 05:15
1

@user3262424: It is hard to say how (or even *whether*) to optimise your *actual* code without seeing it. If you can break your `list` (I *presume* you meant `list`, not `vector`) into `slice`s, and assess at checkpoints whether you continue or break your flow of execution, then you should structure your code accordingly. I've demonstrated how you can time and compare different approaches. That's all I can do with what you have given me. – johnsyweb May 29 '11 at 05:19
@Johnsyweb: I can break my `list` to slices, but don't want to do it as it created copies of the same list. this will take time. instead, I prefer to loop over the original `list`, as no copies are needed. By the way, I am using a `numpy` array, but that doesn't really matter. the logic is what matters here. Thank you. – user3262424 May 29 '11 at 05:22
@user3262424: great! Which bit? – johnsyweb May 29 '11 at 21:54
1

@Johnsyweb: `do_stuff_with()` returning a tuple is a nice idea. I liked your post. – user3262424 May 30 '11 at 17:36
1

Instead of returning a tuple, it could raise an exception which you catch either inside or outside of your loop, as appropriate. – xorsyst Jan 26 '12 at 16:03
@xorsyst: That's a interesting idea. I didn't do this because I didn't consider this [flow exceptional](http://stackoverflow.com/a/77164/78845). Which of Python's `Exception` classes would would you `raise`? – johnsyweb Jan 26 '12 at 21:54
@Johnsyweb: I would create my own subclass of Exception for this, just to be sure I didn't catch anything I didn't want to. You _could_ raise a StopIteration, which you wouldn't then need to catch I think, but it would have to be commented heavily! – xorsyst Jan 27 '12 at 15:00
@xorsyst: "but it would have to be commented heavily" certainly rings alarm bells. Have you read [Clean Code](http://tinyurl.com/CleanCodeBook)? – johnsyweb Jan 27 '12 at 20:50
@Johnsyweb It should ring alarm bells! :) But occasionally something unusual is the best approach, especially if you're optimizing for speed, which is ok providing you comment heavily about what it's doing and why. – xorsyst Jan 30 '12 at 08:37

score 1 · Answer 2 · answered May 29 '11 at 05:08

If you are not going to loop through all of it, then the cost of setting up a new generator (xrange) is quite small.

So the second approach would be faster, if you are sometimes skipping one or two of those loops.

That said, if your list is only 300 big, then the difference is going to be negligible, in the order of milliseconds or microseconds.

Blender · Answer 3 · 2011-05-29T05:20:33.757

If you want to compare speeds, just time them both:

import timeit

chunk1 = '''
sum = 0
for i in xrange(0, 300):
    sum += i
'''

chunk2 = '''
sum = 0
for i in xrange(0, 100):
    sum += i
for i in xrange(100, 200):
    sum += i
for i in xrange(200, 300):
    sum += i
'''

timer1 = timeit.Timer(chunk1)
timer2 = timeit.Timer(chunk2)

print timer1.timeit(100000)
print timer2.timeit(100000)

I get these numbers for 100,000 iterations:

3.44955992699
3.56597089767

As you can see, the second chunk of code is slightly slower.

You might be able to try a while loop and a break statement, so here's what I interpret you as trying to do:

i = 0

while i < limit:
  stop = False

  for j in xrange(i + 100, i + 300):
    if i == foo:
      stop = True
      break

  if stop:  break
  i += 1

Single Vs. Multiple For Loops In Python?

3 Answers3