Geek Answers Handbook

Iterated Function in Python

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

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

The obvious way to do this in Python is with 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.

+6
source share
2 answers

There are several ways to optimize this code:

  • Using itertools.repeat(None, times) to control the number of loops (this avoids creating new unused integer objects at each iteration).

  • You can get speed by putting it in a function or generator (local variables are faster than global variables.

  • You can increase speed by storing intermediate results in a variable, avoiding indexed search [-1] (LOAD_FAST / STORE_FAST is faster than LOAD_CONST -1 and BINARY_SUBSCR).

  • You can improve speed by using the pre-bound method instead of y.append .

For instance:

 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 an example call:

 >>> def double(x): return 2 * x >>> nest(double, 3, 5) [3, 6, 12, 24, 48, 96]

Here is a parsing showing a hard inner loop, using local variables, and an associated 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
+10
source

You can use the 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 switch to a 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 work better on my machine than the decision made, for 2 ms for the generator, 2 ms for the functional and 4 ms for the Raymond code with f = lambda x: x * x , x_0 = 2 and N = 20 .

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

+6
source

More articles:


All Articles