Using % operator to check number of iterations

Question

In my program, I use the function for i in range... and since the number of iterations is very high while the speed is relatively slow (cca "10 i per second"), I start the cycle with

if i % 1000 == 0:
    print(i//1000)

showing the progress of program.

My question is, how complicated is this for Python? Does it actually try to divide i by 1000 on every iteration? I do not believe it has tricks for these situations, the interpreter just blindly follows what is written. A human would look at the last 3 digits to check for divisibility (as computers use binary maths, I could try replacing with 1024).

How is this operation therefore complicated and costly? Is there an easier (not by coding, but by execution) solution?

In terms of minimizing memory consumption, yet providing as precise progress info as possible- I would try to parallelize progress showing, and run it in parallel with your main program. After googling it- this looks like an interesting option: https://stackoverflow.com/a/29703127/11610186 — Grzegorz Skibinski, Jan 01 '20 at 19:38
The `i % 1000` operation is performed on every iteration, yes. — John Gordon, Jan 01 '20 at 19:39
since it's not static value like 1 == 0: yes, the value of i is taken on every iteration and divided by 1000. But it's not slow, it's quite low lvl operation — Zydnar, Jan 01 '20 at 19:39
computer calculate `i % 1000` much faster then human can check if number ends with 3 zeros. So I wouldn't bother this. Computer needs much more time to execute `print()` then checking `i % 1000` so using it to reduce number of `print()` is good idea. — furas, Jan 01 '20 at 19:43
It seems like ultimately you're asking how fast modulo is, right? — wjandrea, Jan 01 '20 at 19:44
Now I see you can go even with lower lvl solution and simply use range( 0, i, 1000 ) — Zydnar, Jan 01 '20 at 19:45
@Zydnar i think they want to iterate through all numbers in the range, just only want to print every 1000 number of lines so they have an idea of the progress its making — Chris Doyle, Jan 01 '20 at 19:47

score 2 · Answer 1 · answered Jan 01 '20 at 20:19

2

Yes. Python does the modulo operation each time. But, optimizing at this level is generally a waste of energy.

If you really need to optimize your code at that level, implement whatever simple approach you find appropriate, and then profile the function to understand where you need to optimize.

#!/usr/bin/env python3
import cProfile
import time

def dowork():
    # This takes SOME time for each iteration (100 usec here)
    time.sleep(0.0001)

def dolog(i):
    if 0 == i % 1000:
        print(i//1000)

def fn():
    for i in range(100000):
        dowork()
        dolog(i)

cProfile.run('fn()')

This results in:

<snip>
98
99
    300104 function calls in 13.412 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000   13.412   13.412 <string>:1(<module>)
     1    0.120    0.120   13.412   13.412 foo.py:13(fn)
100000    0.183    0.000   13.228    0.000 foo.py:5(dowork)
100000    0.060    0.000    0.064    0.000 foo.py:9(dolog)
     1    0.000    0.000   13.412   13.412 {built-in method builtins.exec}
   100    0.004    0.000    0.004    0.000 {built-in method builtins.print}
100000   13.045    0.000   13.045    0.000 {built-in method time.sleep}
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

So for all that logging, this code incurring under 0.5% penalty. Obviously your code is different which is why you profile YOUR code, since you often discover other things that can be improved.

answered Jan 01 '20 at 20:19

Marvin

2,537
24
35

The `tottime` column is the one you're looking at, right? I'm not familiar with cProfile. – wjandrea Jan 01 '20 at 20:37
1

I was actually looking at cumulative time, since I wanted to show that some function doing work will dwarf some logic tests deciding whether to log. The cumulative time in dowork() is 13.228, but most of THAT is just in time.sleep(), so the dowork tottime() -- the time IN dowork(), not in some other function -- is miniscule, since it doesn't actually do any work. Read more about using cProfile at https://docs.python.org/3.8/library/profile.html – Marvin Jan 01 '20 at 21:06
So to use your code (with the cProfile), I just pack my cycle in a function,("def function_name():") and then call the function with "cProfile.run(function_name())" ? – Ferazhu Jan 02 '20 at 01:07
Sorry for digression, but it appears that most of the time was spent on " {method 'index' of 'list' objects} " The program works that way it modifies one item of a list and then searches the index of list in another list of lists. I am creating something which works like a tree (in a chess game), but haven't got enough experience in graphs/trees, so I just add a list of indices of positions (every position has its index) - which position I can get into by making one move. – Ferazhu Jan 02 '20 at 13:35
So, a comment thread like this isn't the place for this discussion. You could ask a NEW question about cProfile with some example code, for example. But, the fact that cProfile tells you your coffee is spending most of is time in list.index is telling you THAT is where you need to optimize, not ```if I % 1000```, my original point. It is work to make an example code fragment for stack overflow, and work to post a question, but doing that work will get you better answers. cProfile is telling you you're spending all your time searching through lists, not a very efficient operation. – Marvin Jan 03 '20 at 09:02
There are many different ways to call cProfile. See the docs at https://docs.python.org/3.8/library/profile.html. The way I called it in this example was just to show a complete usable code fragment. Generally it would be used differently to profile an existing script or module. – Marvin Jan 03 '20 at 09:07

score 0 · Answer 2 · answered Jan 01 '20 at 20:17

The operation if i % 1000 == 0: runs in O(1). Generally if-statements run in O(1) so long as they're simple. (i.e. not containing any complicated functions that recurse or iterate, etc.) This code is as fast as it's going to get. The only thing faster is O(0) operations, meaning your piece of code would be non-existing.

Python blindly checks each iteration to whether i % 1000, and if you think about it, so does a human. One has to keep looking at each iteration to determine for divisibility.

If you're interested in speeding this up, look into your iteration. If you can creatively decrease the amount of loops you make or keep each i type int (as opposed to long, etc. You're already doing this with range), you can decrease the cost of your code. This may not be possible, depending on what your code does.

TL;DR: if i % 1000 == 0 is as simple as it gets. Try decreasing the amount of iterations you have in range to speed your overall code. In some cases, this may not be possible.

But if it works as a standard division, it will be still more complicated than "just looking at the last digits". I am referring to the actual operation time, not the complexity. Obviously, Python is already so slow program that an efficiency of dividing operation is the last of my worries. — Ferazhu, Jan 02 '20 at 01:32

Using % operator to check number of iterations

2 Answers2