I have a python function that I'd like to apply to a value many, many times. I know I can do it with a for loop:
for i in range(N_iter):
val=f(val)
But is there a more efficient way, maybe using itertools or functools?
2 Answers
There's at least two things you can do: use local variables and unroll the loop.
Here's the baseline:
def f(x):
return x+1
N_iter=16777216
val=0
for i in range(N_iter):
val=f(val)
print(val)
On my system, this takes about 0m2.448s.
Here's the code when all references are local, meaning that Python won't have to load and store them each time:
def f(x):
return x+1
def iterate(f, N_iter, val):
for i in range(N_iter):
val=f(val)
print(val)
iterate(f, 16777216, 0)
This takes 0m1.648s.
You can also manually unroll the loop, doing more iterations per jump. Here's 8 (for simplicity it doesn't handle remainders):
def f(x):
return x+1
def iterate(f, N_iter, val):
for i in range(N_iter//8):
val=f(val)
val=f(val)
val=f(val)
val=f(val)
val=f(val)
val=f(val)
val=f(val)
val=f(val)
print(val)
iterate(f, 16777216, 0)
This takes 0m1.327s.
Together, they've sped up this tight loop up by nearly 50%.
When you reach this level of microoptimization, it may be worth rethinking the whole approach or rewriting in a faster language.
Call the function recursively, Set a base condition that gets decremented in every call. cheers
Related