Python: запоминается ли математика?

Question

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

Спасибо.

Answer 1

Python's math.factorial не запоминается, это простой цикл для умножения значений от 1 до вашего аргумента.Если вам нужно запоминание, вам нужно сделать это явно.

Вот простой способ запоминания с использованием метода setdefault словаря.

Answer 2

Найдите math_factorial по этой ссылке, и вы найдете его реализацию в python:

http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup

P.S. Это для python2.6

Answer 3

Математический. Python не запоминается.

Я собираюсь провести вас через несколько примеров проб и ошибок, чтобы понять, почему для получения действительно запоминающейся и работающей факториальной функции вы должны переопределить ее ex-novo с учетом нескольких вещей.

Другой ответ на самом деле не правильный. Здесь

import math
cache = {}
def myfact(x):
    return cache.setdefault(x,math.factorial(x))

линия

return cache.setdefault(x,math.factorial(x))

вычисляет и x, и math.factorial(x) каждый раз, и поэтому вы не получаете улучшения производительности.

Вы можете подумать о том, чтобы сделать что-то вроде этого:

if x not in cache:
    cache[x] = math.factorial(x)
return cache[x]

но на самом деле это тоже неправильно. Да, вы избегаете повторного вычисления факториала того же x, но думаете, например, если вы собираетесь вычислять myfact(1000) и вскоре после этого myfact(999). Они оба рассчитываются полностью, таким образом, не пользуясь преимуществом того факта, что myfact(1000) автоматически вычисляет myfact(999).

Естественно написать что-то вроде этого:

def memoize(f):
    """Returns a memoized version of f"""
    memory = {}
    def memoized(*args):
        if args not in memory:
            memory[args] = f(*args)
        return memory[args]
    return memoized

@memoize
def my_fact(x):
    assert x >= 0
    if x == 0:
        return 1
    return x * my_fact(x - 1)

Это будет работать. К сожалению, вскоре он достигает максимальной глубины рекурсии.

Так как это реализовать?

Вот пример действительно запомненного факториала, который использует преимущества работы факториалов и не использует весь стек рекурсивными вызовами:

# The 'max' key stores the maximum number for which the factorial is stored.
fact_memory = {0: 1, 1: 1, 'max': 1}

def my_fact(num):
    # Factorial is defined only for non-negative numbers
    assert num >= 0

    if num <= fact_memory['max']:
        return fact_memory[num]

    for x in range(fact_memory['max']+1, num+1):
        fact_memory[x] = fact_memory[x-1] * x
    fact_memory['max'] = num
    return fact_memory[num]

Надеюсь, вы найдете это полезным.

EDIT:

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

def memoize(f):
    """Returns a memoized version of f"""
    memory = {}
    def memoized(*args):
        if args not in memory:
            memory[args] = f(*args)
        return memory[args]
    return memoized

@memoize
def my_fact(x, fac=1):
    assert x >= 0
    if x < 2:
        return fac
    return my_fact(x-1,  x*fac)

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

К сожалению, python не поддерживает оптимизацию хвостовой рекурсии, поэтому вы все равно получаете:

RuntimeError: maximum recursion depth exceeded

при высоком значении my_fact.

Answer 4

Я опаздываю на вечеринку, но вот мой 2c по реализации эффективной запоминающейся факториальной функции в Python.Этот подход более эффективен, поскольку он опирается на массивоподобную структуру (то есть list), а не на хеш-контейнер (то есть dict).Никакой рекурсии не требуется (избавляет вас от некоторых накладных расходов при вызове функций Python) и не требуется медленных циклов for.И это (возможно) функционально-чистый, так как не имеет никаких внешних побочных эффектов (то есть он не изменяет глобальную переменную).Он кэширует все промежуточные факториалы, поэтому, если вы уже вычислили factorial(n), вам понадобится O (1), чтобы вычислить factorial(m) для любых 0 <= m <= n и O (mn) для любого m> n.

def inner_func(f):
    return f()


@inner_func
def factorial():
    factorials = [1]

    def calculate_factorial(n):
        assert n >= 0
        return reduce(lambda cache, num: (cache.append(cache[-1] * num) or cache),
                      xrange(len(factorials), n+1), factorials)[n]

    return calculate_factorial