Iterated function in Python

Question

Given a function f( ), a number x and an integer N, I want to compute the List:

y = [x, f(x), f(f(x)), ..., f(f... M times...f(f(x)) ]

An obvious way to do this in Python is the following Python code:

y = [x]
for i in range(N-1):
    y.append(f(y[-1]))

But I want to know if there is a better or faster, way to do this.

Answer 1

There are several ways to optimize this code:

1. It is faster to using itertools.repeat(None, times) to control the number of loops (this avoids creating new, unused integer objects on every iteration).

2. You can gain speed by putting this in a function or generator (local variables are faster than global variables.

3. You can gain speed by saving the intermediate results in a variable, avoiding the [-1] indexed lookup (LOAD_FAST / STORE_FAST is quicker than LOAD_CONST -1 and BINARY_SUBSCR).

4. You can improve speed by using a pre-bound method instead of y.append.

For example:

from itertools import repeat

def nest(func, x, times):
     result = [x]
     result_append = result.append
     for _ in repeat(None, times):
         x = func(x)
         result_append(x)
     return result

Here is a sample call:

>>> def double(x):
        return 2 * x

>>> nest(double, 3, 5)
[3, 6, 12, 24, 48, 96]

Here is the disassembly showing the tight inner-loop, use of local variables, and the bound method:

>>> from dis import dis
>>> dis(nest)
  2           0 LOAD_FAST                1 (x)
              3 BUILD_LIST               1
              6 STORE_FAST               3 (result)

  3           9 LOAD_FAST                3 (result)
             12 LOAD_ATTR                0 (append)
             15 STORE_FAST               4 (result_append)

  4          18 SETUP_LOOP              45 (to 66)
             21 LOAD_GLOBAL              1 (repeat)
             24 LOAD_CONST               0 (None)
             27 LOAD_FAST                2 (times)
             30 CALL_FUNCTION            2
             33 GET_ITER            
        >>   34 FOR_ITER                28 (to 65)
             37 STORE_FAST               5 (_)

  5          40 LOAD_FAST                0 (func)
             43 LOAD_FAST                1 (x)
             46 CALL_FUNCTION            1
             49 STORE_FAST               1 (x)

  6          52 LOAD_FAST                4 (result_append)
             55 LOAD_FAST                1 (x)
             58 CALL_FUNCTION            1
             61 POP_TOP             
             62 JUMP_ABSOLUTE           34
        >>   65 POP_BLOCK           

  7     >>   66 LOAD_FAST                3 (result)
             69 RETURN_VALUE 

Answer 2

You can use a generator:

import itertools

def apply_apply(f, x_0):
    x = x_0
    while True:
        yield x
        x = f(x)

....

y = list(itertools.islice(apply_apply(f, x), N))

Another way is to go the fully functional route:

from functools import reduce

y = list(reduce(lambda x, f: x + [f(x[-1])], [[x_0]] + [f] * (N - 1)))

As a side note, both solutions perform better on my machine than the accepted solution, being 2ms for the generator, 2ms for the functional and 4ms for Raymond's code with f = lambda x: x * x, x_0 = 2 and N = 20.

For lambda x: 2 * x Raymond's version is slightly faster than the generator approach and a lot faster than the functional variant. It seems to depend on the complexity of f, though I don't know how ...