2

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?

user3433489
  • 911
  • 2
  • 10
  • 24
  • Does this answer your question? [Are list-comprehensions and functional functions faster than "for loops"?](https://stackoverflow.com/questions/22108488/are-list-comprehensions-and-functional-functions-faster-than-for-loops) – my_name Aug 25 '20 at 02:00
  • 1
    How would one write this as a list comprehension? – user3433489 Aug 25 '20 at 02:01
  • You can try multithreading (https://docs.python.org/3/library/multiprocessing.html) assuming the function is thread safe. – Mike67 Aug 25 '20 at 02:04
  • 1
    @Mike67 How do you multithread something as inherently sequential as this? – that other guy Aug 25 '20 at 02:06
  • I'm more interested in a single threaded solution. Also, how would it work since iteration (i) depends on iteration (i-1)? – user3433489 Aug 25 '20 at 02:06
  • If you want low runtime instead of succinct expression, then the standard tips regarding function local variables and unrolling apply. – that other guy Aug 25 '20 at 02:11
  • I can't think of a way this can be sped up in the general case. Mostly vectorization/GPU compute can be used for acceleration, but I don't see how these can help in the general case. – anon01 Aug 25 '20 at 02:14
  • If the problem lends itself, memoization might be useful... but that's not very general. – anon01 Aug 25 '20 at 02:16
  • @thatotherguy can you explain what you mean by local variables and unrolling? – user3433489 Aug 25 '20 at 17:11

2 Answers2

1

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.

that other guy
  • 116,971
  • 11
  • 170
  • 194
  • Thank you. I didn't know about these tricks. You're right though, another language would be better, or using Numba. – user3433489 Aug 25 '20 at 18:50
-2

Call the function recursively, Set a base condition that gets decremented in every call. cheers

Khattak
  • 3
  • 3
  • Do you think that will be more efficient? Why? – Mark Aug 25 '20 at 02:11
  • Though memoization makes recursion useful, however, iterative based methods are always faster. I mistook the question for space efficiency. – Khattak Aug 26 '20 at 03:00