python 3: настройка переменной один раз внутри функции, которая вызывается несколько раз [дубликат]

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

см. http : //scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Пример Memoization Fibonacci в Python:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]

Memoization сохраняет результаты дорогостоящих вычислений и возвращает кешированный результат, а не непрерывно пересчитывает его.

Вот пример:

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

Более полное описание можно найти в записи wikipedia в memoization .

Решение, которое работает как с аргументами positional, так и с ключевыми словами независимо от порядка, в котором были переданы ключевые слова args (используя inspect.getargspec ):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

Аналогичный вопрос: Идентификация эквивалентных функций функции varargs для memoization в Python

Запоминание - это преобразование функций в структуры данных. Обычно требуется, чтобы преобразование происходило постепенно и лениво (по запросу данного элемента домена - или «ключ»). В ленивых функциональных языках это ленивое преобразование может происходить автоматически, и, таким образом, мемонирование может быть реализовано без (явных) побочных эффектов.

Давайте не будем забывать о встроенной функции hasattr, для тех, кто хочет заниматься ремеслом. Таким образом, вы можете хранить кеш-память внутри определения функции (в отличие от глобального).

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]

Новое для Python 3.2 - functools.lru_cache . По умолчанию он кэширует только 128 последних вызовов, но вы можете установить maxsize на None, чтобы указать, что кеш никогда не истекает:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Эта функция сама по себе очень медленно, попробуйте fib(36), и вам придется подождать около десяти секунд.

Добавление аннотации lru_cache гарантирует, что если функция была вызвана в последнее время для определенного значения, она не будет компрометировать это значение, а использовать кешированный предыдущий результат. В этом случае это приводит к значительному улучшению скорости, в то время как код не загроможден деталями кеширования.

Я нашел это чрезвычайно полезным

def memoize(function):
    from functools import wraps

    memo = {}

    @wraps(function)
    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv
    return wrapper


@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(25)

Другие ответы охватывают то, что хорошо. Я не повторяю этого. Просто некоторые моменты, которые могут быть полезны для вас.

Как правило, memoisation - это операция, которую вы можете применить к любой функции, которая что-то вычисляет (дорого) и возвращает значение. Из-за этого он часто реализуется как декоратор . Реализация прост, и это будет нечто подобное

memoised_function = memoise(actual_function)

или выражено в качестве декоратора

@memoise
def actual_function(arg1, arg2):
   #body

Мемонирование эффективно относится к запоминанию («воспоминания» → «меморандум» → для запоминания) результаты вызовов методов на основе входных данных метода, а затем возврат запоминаемого результата, а не повторение вычисления результата. Вы можете думать об этом как кэш для результатов метода. Более подробную информацию см. На стр. 387 для определения в . Введение в алгоритмы (3e), Cormen и др.

. Простой пример вычисления факториалов с использованием memoization в Python был бы чем-то вроде это:

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

Вы можете усложниться и инкапсулировать процесс memoization в класс:

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)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

Затем:

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

factorial = Memoize(factorial)

Функция известный как « decorators », был добавлен в Python 2.4, который позволяет вам просто написать следующее, чтобы выполнить одно и то же:

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

Библиотека декораторов питона имеет аналогичный декоратор, называемый memoized , который немного более устойчив, чем класс Memoize, показанный здесь.

Вот решение, которое будет работать со списком или аргументом типа dict без завивания:

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

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

if is_instance(x, set):
    return make_tuple(sorted(list(x)))

Просто хотел добавить к уже предоставленным ответам, библиотека декораторов Python имеет несколько простых, но полезных реализаций, которые также могут memoize «unhashable types», в отличие от functools.lru_cache.