functools: cache, partial, reduce and more

Counting the down-and-right routes across an 11 × 11 grid takes 369,511 calls of a plain recursive function and 120 calls with @cache, one decorator line from functools, the standard library’s module of tools that take a function and give you a better one. cache and lru_cache remember what a function returned for each set of arguments, so a repeated call costs one dictionary lookup instead of the work. partial pre-fills some arguments and hands back a function that needs fewer, and Python 3.14’s Placeholder can leave a positional slot open. reduce folds a sequence into one value.

Below you will step through a cache’s hits and misses and an LRU cache dropping entries, see what makes a function unsafe to cache, compute an attribute once with cached_property, fill a partial object’s slots, and meet singledispatch, total_ordering and cmp_to_key.

@cache answers a repeated call from memory

Start with a small grid. The routes to a cell are the routes to the cell above it plus the routes to the cell on its left, and a cell on the top or left edge has exactly one route. paths() prints a line each time its body runs, which with @cache happens only on a cache misscache miss: A call whose arguments a cache has not stored yet, so the function runs and its result is stored. cache_info() counts them as misses.:

from functools import cache


@cache
def paths(r, c):
    print(f"  computing paths({r}, {c})")   # runs only on a miss
    if r == 0 or c == 0:
        return 1
    return paths(r - 1, c) + paths(r, c - 1)


print("routes:", paths(2, 2))
print(paths.cache_info())

  computing paths(2, 2)
  computing paths(1, 2)
  computing paths(0, 2)
  computing paths(1, 1)
  computing paths(0, 1)
  computing paths(1, 0)
  computing paths(2, 1)
  computing paths(2, 0)
routes: 6
CacheInfo(hits=1, misses=8, maxsize=None, currsize=8)

Eight lines were printed for nine calls. Step through the calls in the order they happen and find the one that printed nothing:

The second request for paths(1, 1) was a cache hitcache hit: A call a cache answers from a result it stored before, without running the function. cache_info() counts them as hits.: the stored answer came back without running the function, and the calls below it never happened. On a bigger grid the saving grows fast:

from functools import cache

calls = {"plain": 0, "cached": 0}


def paths(r, c):
    """Routes from (0, 0) to (r, c) that move only down or right."""
    calls["plain"] += 1
    if r == 0 or c == 0:
        return 1
    return paths(r - 1, c) + paths(r, c - 1)


@cache
def paths_cached(r, c):
    calls["cached"] += 1
    if r == 0 or c == 0:
        return 1
    return paths_cached(r - 1, c) + paths_cached(r, c - 1)


print("plain: ", paths(10, 10), "after", f"{calls['plain']:,}", "calls")
print("cached:", paths_cached(10, 10), "after", calls["cached"], "calls")
print(paths_cached.cache_info())

# A bigger grid reuses the 120 answers already stored.
print(paths_cached(30, 30), paths_cached.cache_info())

plain:  184756 after 369,511 calls
cached: 184756 after 120 calls
CacheInfo(hits=81, misses=120, maxsize=None, currsize=120)
118264581564861424 CacheInfo(hits=842, misses=960, maxsize=None, currsize=960)

Without the cache, paths(10, 10) takes 369,511 calls; with it, 120, one for each cell that is ever asked for. The misses are the calls that ran the function, and the hits the calls answered from the cache, 81 here. The call paths_cached(30, 30) afterwards reused the 120 stored answers and added 840 more, a cache of 960 entries in all. Its answer is exact, because Python’s integers have no size limit: there are 118,264,581,564,861,424 routes. Press Edit, change paths_cached(30, 30) to paths_cached(40, 40) and run it: the cache grows to 1,680 entries.

An LRU cache keeps the most recently used results

functools.cache is lru_cache(maxsize=None): it never forgets, which makes it a little smaller and faster than a cache with a limit, and it grows for as long as new arguments arrive. functools.lru_cache(maxsize=128), the default size, keeps only the most recently used results. When a new result arrives and the cache is full, it drops the least recently usedleast recently used (LRU): The stored entry whose last use is the longest ago. A full lru_cache drops it to make room for a new result. entry, the one whose last call is the longest ago:

The program follows that flow with a cache of three entries. Its function prints a line only when it runs, on a miss:

from functools import lru_cache


@lru_cache(maxsize=3)
def shelf_price(item):
    print(f"  looking up {item}")   # runs only on a miss
    return len(item) * 10


for item in ["tea", "rice", "tea", "salt", "dal", "rice", "tea"]:
    shelf_price(item)
print(shelf_price.cache_info())
print(shelf_price.cache_parameters())
shelf_price.cache_clear()
print(shelf_price.cache_info())

  looking up tea
  looking up rice
  looking up salt
  looking up dal
  looking up rice
  looking up tea
CacheInfo(hits=1, misses=6, maxsize=3, currsize=3)
{'maxsize': 3, 'typed': False}
CacheInfo(hits=0, misses=0, maxsize=3, currsize=0)

Step through the seven calls and watch the three entries, from the most to the least recently used:

The second tea is a hit. When dal arrives, the cache holds rice, tea and salt, and rice was used longest ago, so it is dropped; the next rice is a miss again and drops tea, and the last tea drops salt. One hit in seven calls: a hit ratio, hits / (hits + misses), of about 14 %, which says this cache is too small for the way it is used. cache_info() is the number to watch when you choose maxsize; cache_parameters() shows the settings and cache_clear() empties the cache.

Cache only pure functions with hashable arguments

A cache returns the stored result instead of running the function, so it is only correct for a pure functionpure function: A function whose result depends only on its arguments and which changes nothing outside itself, such as gcd(a, b). Only such a function is safe to cache.: one whose result depends on nothing but its arguments, unlike one that reads the clock or a file, and which has no side effects, such as writing to a file or sending a message. Even such a function can trip over the cache. Step through the first trap, a cached function that returns a list:

from functools import cache


@cache
def tags_for(product):
    return ["new", "sale"]


first = tags_for("lamp")
first.append("clearance")
second = tags_for("lamp")
print(second, first is second)

['new', 'sale', 'clearance'] True

The cache stores the object it returned, not a copy, so the caller’s append() reached every later caller. That trap and three others, in one program:

from functools import lru_cache


@lru_cache(maxsize=None)
def tags_for(product):
    return ["new", "sale"] if product == "lamp" else ["new"]


first = tags_for("lamp")
first.append("clearance")       # a caller changes the list it was given ...
print(tags_for("lamp"))         # ... and the cached answer changed for every caller

try:
    tags_for(["lamp"])          # the arguments become the key, so they must be hashable
except TypeError as err:
    print("TypeError:", err)


@lru_cache(maxsize=None)
def area(width, height):
    return width * height


area(2, 3)
area(width=2, height=3)         # the same call to you, another key to the cache
area(height=3, width=2)
print(area.cache_info())


@lru_cache(maxsize=None)
def half(x):
    return x / 2


@lru_cache(maxsize=None)
def add(x, y):
    return x + y


half(4)
half(4.0)                       # one int argument: a separate entry even without typed=True
add(1, 2)
add(1.0, 2.0)                   # two arguments: (1, 2) and (1.0, 2.0) share one entry
print(half.cache_info().currsize, add.cache_info().currsize)


@lru_cache(maxsize=None, typed=True)
def add_typed(x, y):
    return x + y


add_typed(1, 2)
add_typed(1.0, 2.0)             # typed=True: separate entries for int and float, always
print(add_typed.cache_info().currsize)

['new', 'sale', 'clearance']
TypeError: unhashable type: 'list'
CacheInfo(hits=0, misses=3, maxsize=None, currsize=3)
2 1
2

1. A mutable result is shared. tags_for("lamp") returns the same list object on every call, so one caller’s append() changed the answer for everyone. Return a tuple or a frozenset, or a copy.
2. The arguments are the key, so they must be hashablehashable: A value that can be a dict key or a set item, because its hash never changes while it exists: numbers, strings and tuples of hashable values are hashable; lists, dicts and sets are not.. A list argument raises TypeError: unhashable type. Pass a tuple or a frozenset instead.
3. The same call can be spelt in different ways. area(2, 3), area(width=2, height=3) and area(height=3, width=2) are three entries: the documentation says that different argument patterns may be cached separately, and here they were.
4. Equal values of different types. With typed=True, an int and an equal float always get separate entries. Without it, the documentation says they are usually treated as one call, with exceptions such as int and str, and the run shows both cases: a single argument, 4 and then 4.0, got two entries anyway, while the pairs (1, 2) and (1.0, 2.0) shared one. Code should not depend on either.

Two more rules follow from the documentation. The cache keeps references to its arguments and results until they are dropped or the cache is cleared, so an unbounded cache in a program that runs for weeks keeps everything it has ever seen. And a cached method includes self in its key, so the cache keeps every instance alive; the Programming FAQ discusses the options. The caches are thread-safe, in that the stored data stays consistent, but two threads that ask for a new value at the same moment may both run the function.

A cached property is computed once per instance

@cached_property turns a method into an attribute that is computed the first time it is read and then stored in the instance like any other attribute:

import statistics
from functools import cached_property


class Marks:
    def __init__(self, values):
        self.values = values

    @cached_property
    def summary(self):
        print("  (computing the summary)")
        return statistics.mean(self.values), max(self.values)


m = Marks([62, 75, 81, 94, 58])
print(m.summary)
print(m.summary)                 # read from the instance: no second computation
print("summary" in vars(m))      # the value now lives in the instance's __dict__

m.values.append(100)
print(m.summary)                 # stale: the cache does not know the list changed
del m.summary                    # deleting the attribute clears it
print(m.summary)

  (computing the summary)
(74, 94)
(74, 94)
True
(74, 94)
  (computing the summary)
(78.33333333333333, 100)

Step through the reads of m.summary and watch where the value lives:

The second read printed nothing: the value was already in the instance’s __dict__. Because it is only computed once, it does not notice that values changed later; deleting the attribute clears it, and the next read computes it again. It needs a writable __dict__, so it does not work on a class with __slots__ that leaves __dict__ out. Since Python 3.12 it takes no lock, so two threads may both compute the value the first time. For a method whose result depends on its arguments, not just on the instance, the Programming FAQ’s advice on caching method calls applies.

partial() pre-fills arguments, and Placeholder keeps a slot open

partial(func, *args, **keywords) returns a partial objectpartial object: What functools.partial() returns: a callable that holds a function and some of its arguments, in .func, .args and .keywords, and adds them to the arguments of each call., a callable that calls func with those arguments already filled in, followed by whatever you pass when you call it:

from functools import Placeholder, partial

square = partial(pow, exp=2)        # fixes a keyword argument
from_binary = partial(int, base=2)
print(square(12), from_binary("101101"))
print(square.func, square.args, square.keywords)

# str.replace takes its arguments by position only, so keywords cannot pre-fill them.
try:
    partial(str.replace, old=" ", new="-")("learn python")
except TypeError as err:
    print("TypeError:", err)

# New in 3.14: Placeholder keeps a positional slot open for the call to fill.
slugify = partial(str.replace, Placeholder, " ", "-")
print(slugify("learn python fast"))
cube = partial(pow, Placeholder, 3)
print(cube(4), cube)

144 45
<built-in function pow> () {'exp': 2}
TypeError: replace() takes at least 2 positional arguments (0 given)
learn-python-fast
64 functools.partial(<built-in function pow>, Placeholder, 3)

partial(pow, exp=2) is a squaring function and partial(int, base=2) reads binary numbers. The partial object keeps the function and the arguments in func, args and keywords, and the values are fixed when you create it, which is why it fixes the late-binding trap of functions built in a loop.

Keywords cannot fill parameters that are positional-only, such as the old and new of str.replace(), as the TypeError shows. Positional arguments are filled from the left, so before Python 3.14 partial could not pre-fill the second and third while leaving the first open. functools.Placeholder, new in 3.14, keeps a slot open. Step through slugify("learn python fast") and watch the slots:

partial(str.replace, Placeholder, " ", "-") waits for the string to work on and replaces its spaces with hyphens, and partial(pow, Placeholder, 3) cubes whatever it is given.

reduce() folds a sequence into one value

reduce(function, iterable, initial) produces a foldfold: Combining a sequence into one value two items at a time: reduce(add, [3, 8, 1]) works out (3 + 8) + 1. sum(), max() and math.prod() are folds with names of their own. More in “Lambdas and higher-order functions”: it combines the first two items with the function, then that result with the next item, until one value is left:

import operator
from functools import reduce

digits = [4, 0, 9, 6]
print(reduce(lambda number, d: number * 10 + d, digits))   # ((4*10 + 0)*10 + 9)*10 + 6

settings = [{"theme": "light", "font": 14}, {"font": 16}, {"theme": "dark"}]
print(reduce(operator.or_, settings, {}))                  # later dicts win

print(reduce(operator.add, [], initial=0))                 # initial by keyword: 3.14

4096
{'theme': 'dark', 'font': 16}
0

Folding the digits 4, 0, 9 and 6 with number * 10 + d builds the number 4,096 one digit at a time. Folding a list of settings dictionaries with operator.or_, the | operator, merges them so that later settings win. Step through the merge:

The initial value {} makes an empty list give an empty dictionary instead of an error, and it takes the place of a first item, so the merge makes one | for each of the three dictionaries. Since Python 3.14, initial can also be given by keyword, as the program’s last line does. When a built-in does the job, as sum(), max(), math.prod() and "".join() do, it is clearer than reduce().

singledispatch picks an implementation by the argument’s type

@singledispatch turns a function into a generic functiongeneric function: A function with one implementation per type, chosen at each call from the type of an argument. functools.singledispatch makes one that dispatches on the first argument.: it chooses which implementation to run from the type of its first argument. You register an implementation for a type with @pretty.register, and the type comes from the annotation of the first parameter:

from functools import singledispatch


@singledispatch
def pretty(value, indent=0):
    """Fallback for any type without its own implementation."""
    return " " * indent + repr(value)


@pretty.register
def _(value: int, indent=0):
    return " " * indent + f"{value:,}"


@pretty.register
def _(value: list, indent=0):
    inner = [pretty(item, indent + 2) for item in value]
    return "\n".join([" " * indent + "[", *inner, " " * indent + "]"])


@pretty.register
def _(value: dict, indent=0):
    lines = [" " * indent + "{"]
    for key, item in value.items():
        lines.append(" " * (indent + 2) + f"{key}:")
        lines.append(pretty(item, indent + 4))
    lines.append(" " * indent + "}")
    return "\n".join(lines)


print(pretty({"orders": [1200, 75000], "city": "Pune", "paid": True}))
print("bool uses the int version:", pretty.dispatch(bool) is pretty.dispatch(int))
print("str falls back to object:", pretty.dispatch(str) is pretty.dispatch(object))
print(sorted(t.__name__ for t in pretty.registry))

{
  orders:
    [
      1,200
      75,000
    ]
  city:
    'Pune'
  paid:
    1
}
bool uses the int version: True
str falls back to object: True
['dict', 'int', 'list', 'object']

Step through the values of the order and the implementation each one reaches:

The dictionary, its list and its integers each reached their own implementation, and the string fell back to the original function, the one registered for object. Look at paid: True was printed as 1, because bool is a subclass of int and dispatch follows subclasses. Registering an implementation for bool would fix it, since the most specific type wins. pretty.registry lists every registered type. For methods, functools.singledispatchmethod does the same and dispatches on the first argument after self.

Four comparisons from one method, and a key from a comparison

@total_ordering is a class decorator: give a class __eq__() and one ordering method such as __lt__(), and it supplies the other three comparisons. cmp_to_key() adapts an old-style comparison functioncomparison function: A function of two items that returns a negative number, zero or a positive number for less, equal or greater. functools.cmp_to_key() turns one into a key function., one that takes two items and returns a negative number, zero or a positive number, into a key function that sorted() accepts:

from functools import cmp_to_key, total_ordering


@total_ordering
class Version:
    """Version numbers such as 3.9 and 3.14, compared part by part."""

    def __init__(self, text):
        self.text = text
        self.parts = tuple(int(p) for p in text.split("."))

    def __eq__(self, other):
        return self.parts == other.parts

    def __lt__(self, other):
        return self.parts < other.parts

    def __repr__(self):
        return self.text


a, b = Version("3.9"), Version("3.14")
print(a < b, a <= b, a > b, a >= b)          # <=, > and >= were filled in
print(sorted([Version("3.14"), Version("3.9"), Version("3.10.2"), Version("3.10")]))

counts = {"compare": 0, "key": 0}


def compare(x, y):   # an old-style comparison: negative, zero or positive
    counts["compare"] += 1
    px, py = tuple(map(int, x.split("."))), tuple(map(int, y.split(".")))
    return (px > py) - (px < py)


def version_key(v):
    counts["key"] += 1
    return tuple(map(int, v.split(".")))


versions = [f"{major}.{minor}" for major in range(1, 5) for minor in (12, 3, 0, 7, 10)]
assert sorted(versions, key=cmp_to_key(compare)) == sorted(versions, key=version_key)
print(len(versions), "versions:", counts)

True True False False
[3.9, 3.10, 3.10.2, 3.14]
20 versions: {'compare': 62, 'key': 20}

Version defines only __eq__() and __lt__(), yet <=, > and >= work, and 3.10 correctly sorts after 3.9, which plain text comparison gets wrong. The counts show why a key function is the better choice whenever one exists:

Use cmp_to_key() when the order can only be described by comparing two items with each other, or when a library hands you a comparison function, as locale.strcoll() does for language-aware text.

Practise: count routes and build the largest number

The exercise has two functions. count_paths() counts the down-and-right routes across a grid with blocked cells, and needs a cache, because one sample test uses an 18 × 18 grid with more than two billion routes. largest_number() lays price tags side by side to make the largest number and needs a comparison function through cmp_to_key():

from functools import cache, cmp_to_key, lru_cache


def count_paths(rows, cols, blocked=frozenset()):
    """Count the down-and-right routes from (0, 0) to (rows - 1, cols - 1) that avoid the blocked cells."""
    return 0


def largest_number(numbers):
    """Return, as a string, the largest number the numbers make when written side by side."""
    return "".join(str(n) for n in sorted(numbers, reverse=True))

from tools import count_paths, largest_number


def test_small_grids():
    """counts the routes of small open grids"""
    assert count_paths(1, 1) == 1
    assert count_paths(2, 2) == 2
    assert count_paths(3, 3) == 6
    assert count_paths(3, 7) == 28


def test_blocked_cells():
    """routes avoid the blocked cells"""
    assert count_paths(3, 3, frozenset({(1, 1)})) == 2
    assert count_paths(3, 3, frozenset({(0, 1), (1, 0)})) == 0
    assert count_paths(4, 4, frozenset({(1, 2), (2, 1)})) == 2


def test_blocked_start_or_end():
    """a blocked start or end leaves no route"""
    assert count_paths(3, 3, frozenset({(0, 0)})) == 0
    assert count_paths(3, 3, frozenset({(2, 2)})) == 0


def test_large_grid():
    """an 18 x 18 grid finishes quickly with a cache"""
    assert count_paths(18, 18) == 2_333_606_220
    assert count_paths(18, 18, frozenset({(9, 9), (3, 14)})) == 1_707_404_420


def test_largest_number():
    """orders the tags so that the number is as large as possible"""
    assert largest_number([7, 70, 76, 4, 9]) == "9776704"
    assert largest_number([12, 121]) == "12121"
    assert largest_number([5]) == "5"
    assert largest_number([10, 2]) == "210"


def test_zeros():
    """tags that are all 0 make "0" """
    assert largest_number([0, 0, 0]) == "0"
    assert largest_number([0, 1]) == "10"

Finally, practise on caches, partial, folds and dispatch. The questions start where your answers so far are weakest, move up a level after each right answer, and explain each choice as soon as you make it:

Interview questions

Fresher to 2–5 years · What is the difference between functools.cache and functools.lru_cache?

Both are decorators that store a function’s results in a dictionary keyed by its arguments, so a repeated call with the same arguments returns the stored result without running the function. functools.cache, added in Python 3.9, is the same as lru_cache(maxsize=None): it never drops anything, which makes it smaller and faster, but it grows as long as new arguments arrive. lru_cache keeps at most maxsize results, 128 by default, and drops the least recently used one when it is full; typed=True caches arguments of different types separately. Both offer cache_info() and cache_clear(), need hashable arguments, and suit only functions whose results depend on their arguments alone. Choose cache for a bounded set of inputs, such as the states of a recursion, and a sized lru_cache for open-ended input.

Key takeaways

• @cache remembers every result and never forgets; @lru_cache(maxsize=n) keeps the n most recently used, and cache_info()’s hits, misses and hit ratio tell you whether a cache helps.
• Cache only pure functions with hashable arguments, return immutable results, and remember that the cache keeps its arguments and results, and the instances of cached methods, alive.
• @cached_property computes an attribute once per instance; delete the attribute to recompute it.
• partial() fixes arguments now and returns a function that needs fewer; Placeholder, new in 3.14, leaves a positional slot open.
• reduce() folds a sequence; singledispatch picks an implementation by type; total_ordering fills in comparisons; cmp_to_key() turns a comparison function into a key, at the price of more calls.