Minimizing the number of costly function calls when the parameters remain the same (python)

Question

Suppose that there is a function `costly_function_a(x)` such that: - it is very costly in terms of execution time; - it returns the same output whenever the same `x` is fed to it; and - it does not perform "additional tasks" besides returning an output. In these conditions, instead of calling the function twice in a row with the same `x`, we can store the result in a temporary variable, then use that variable to do these computations. Now suppose that there are some functions (`f(x)`, `g(x)` and `h(x)` in the example below) that call `costly_function_a(x)`, and that some of these functions may call each others (in the example below, `g(x)`and `h(x)` both call `f(x)`). In this case, using the simple method mentioned above still results in repeated calls to `costly_function_a(x)` with the same `x` (see `OkayVersion` below). I did found a way to minimize the number of calls, but it is "ugly" (see `FastVersion` below). Any ideas of a better way to do this? ``` #Dummy functions representin…

Accepted Answer

What you are looking for is a LRU cache; only most-recently used items are cached, limiting memory usage to balance invocation cost with memory requirements.

As your costly function is invoked with different values for `x`, up to a number of return values (per unique `x` value) is cached, with the least-recently used cache results discarded when the cache is full.

As of Python 3.2, the standard library comes with a decorator implementation: `@functools.lru_cache()`:

```
from functools import lru_cache

@lru_cache(16)  # cache 16 different `x` return values
def costly_function_a(x):
    print("costly_function_a has been called.")
    return x #Dummy operation.

@lru_cache(32)  # cache 32 different `x` return values
def costly_function_b(x):
    print("costly_function_b has been called.")
    return 5.*x #Dummy operation.
```

A backport is available for earlier versions, or pick one of the other available libraries that can handle LRU caches avaible on PyPI.

If you only ever need to cache one most recent item, create your own decorator:

```
from functools import wraps

def cache_most_recent(func):
    cache = [None, None]
    @wraps(func)
    def wrapper(*args, **kw):
        if (args, kw) == cache[0]:
            return cache[1]
        cache[0] = args, kw
        cache[1] = func(*args, **kw)
        return cache[1]
    return wrapper

@cache_most_recent
def costly_function_a(x):
    print("costly_function_a has been called.")
    return x #Dummy operation.

@cache_most_recent
def costly_function_b(x):
    print("costly_function_b has been called.")
    return 5.*x #Dummy operation.
```

This simpler decorator has less overhead than the more featureful `functools.lru_cache()`.

Minimizing the number of costly function calls when the parameters remain the same (python)

Solution

Problem

Related problems