Мемоизация и рекурсия в Python

Question

Существует множество рекурсий, где может помочь мемоизация. Хороший пример QHofstadter: Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2))

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

class Memoize:

    def __init__(self, start_dict, limit, gen_func):
        self.__memo_dict = start_dict
        self.__limit = limit
        self.__counter = 0
        # self.__func = gen_func ????


    def __iter__(self):
        return self

    def __next__(self):
        if self.__counter < self.__limit:
            self.__counter += 1
            # Уже есть в словаре:
            if self.__counter in self.__memo_dict:
                return self.__memo_dict[self.__counter]
            # Еще нет:
            # return gen_func(self.__counter)????
        else:
            raise StopIteration
    
def gen_func(num):
        return gen_func(num - gen_func(num - 1)) + \
               gen_func(num - gen_func(num - 2))

Первая непонятность при передаче функции. Хочется именно не делать ее частью класса, а передавать. Но как это сделать правильно? Ну и второе собственно рекурсия при вызове __next__ Что-то она не идет...
PS Тема интересная, мемоизация как класс еще не попадалась в статьях. Если сделаем, думаю многим пригодится.

Answer 1

В интеренете уже есть примеры инкапсуляции процесса мемоизации в класс в Python. Далее подробно опишу, как это происходит.

Создаем класс для процесса мемоизации:

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

Используем декоратор для "красивой" мемоизации рекурсивной функции для нахождения факториала:

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

# написав декоратор избегаем написания factorial = Memoize(factorial)

К слову, в PythonDecoratorLibrary можно найти более оптимизированный вариант декоратора @memoize, чем описанный выше.

БЛОГ НА HUSL

Мемоизация и рекурсия в Python

Ответы (1 шт):