Функциональная мемоизация: передача заранее вычисленных значений

У меня есть такая функция в моей библиотеке, которая зависит от большого подмножества входных данных, которые должны быть заранее вычислены:

@cache
def f(n, precompute):
    if n < len(precompute): 
        return precompute[n]

    # рекурсивные вычисления, которые запоминаются при возвращении
    return some_compute(f(n-1, precompute))

Какой самый удобный для пользователя способ передать заранее вычисленный список, используя мемоизацию functools.cache, не кэшируя при этом сам precompute?

Мои идеи:

Просто сделать precompute глобальной переменной/переменной внешней области (нечистый, глобальная переменная должна существовать в модуле заранее Как создать переменные на уровне модуля в Python?)
Сделать precompute атрибутом функции, чтобы использовать его в качестве “аргумента”, обходя кэширование (работает, потому что функция является объектом)
Написать специальный декоратор для мемоизации, который основан только на первом аргументе (предложено в Кэширование результатов функций Python, используя только подмножество аргументов в качестве идентификатора)
Преобразовать это в класс, чтобы precompute стал атрибутом экземпляра или атрибутом класса (это то, что делает sympy.sieve?)
Загрузить cache(f) значениями precompute. Я думаю, что это менее эффективно, так как кэш будет словарем, в то время как precompute является простым списком размером 10^7
Создать внутреннюю вспомогательную рекурсивную функцию с одним аргументом, которая использует precompute во внешней области (я думаю, что именно это сделает учебник по алгоритмам. Я не уверен, сохраняется ли кэш при нескольких внешних вызовах)

Содержание

Ответ
1. Использование глобальной переменной
2. Атрибут функции
3. Особый декоратор для мемоизации
4. Использование класса
5. Кэширование с помощью cache
6. Вложенная функция
Рекомендация

Ответ

Привет! Для решения вашей задачи о функции с мемоизацией и передачей предвычисленных значений можно рассмотреть несколько подходов, каждый из которых имеет свои плюсы и минусы. Давайте разберем ваши идеи и предложим наиболее удобное решение.

1. Использование глобальной переменной

Использование глобальной переменной — это простой способ, однако он не является чистым и может привести к проблемам с тестируемостью и предсказуемостью кода, особенно если функция будет использоваться в многопоточном окружении или в разных частях приложения.

2. Атрибут функции

Вы можете сделать precompute атрибутом функции. Это также довольно удобный способ, но может быть неочевидным для пользователей, которые не ожидают видеть состояние функции через атрибуты:

from functools import cache

def f(n):
    if n < len(f.precompute):
        return f.precompute[n]
    return some_compute(f(n - 1))

f.precompute = []  # Предварительную обработку можно установить перед вызовом функции

3. Особый декоратор для мемоизации

Создание специального декоратора, который будет кэшировать результаты, основанные только на первом аргументе, может быть более гибким, однако это требует больше времени на реализацию.

4. Использование класса

Переписывание функции как класса, чтобы precomputed стал атрибутом экземпляра, делает управление состоянием более прозрачным и предоставляет возможности расширения:

class Calculator:
    def __init__(self, precompute):
        self.precompute = precompute
        self.cache = {}

    def f(self, n):
        if n in self.cache:
            return self.cache[n]
        if n < len(self.precompute):
            return self.precompute[n]

        result = some_compute(self.f(n - 1))
        self.cache[n] = result
        return result

5. Кэширование с помощью `cache`

Вы правы, что использование cache с переданными значениями может затратным, если precompute является простым списком. Это может увеличить потребление памяти и усложнить поиск значений.

6. Вложенная функция

Создание внутренней вспомогательной функции, которая будет использовать precompute из внешней области видимости, является самым простым и элегантным решением, которое сохраняет чистоту кода:

from functools import cache

def f(precompute):
    @cache
    def helper(n):
        if n < len(precompute):
            return precompute[n]
        return some_compute(helper(n - 1))

    return helper