Memoization In Python

Question

Мне очень понравилась бы ваша помощь с пониманием этого использования Memoization в Python. Я новичок в Python, и я не уверен, как понять этот синтаксис.

def fib_mem(n): 
    return fib_mem_helper(n,[0,1]+[-1]*(n-1)) 

def fib_mem_helper(i,mem): 
    if mem[i] == -1: 
     mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem) 
     return mem[i] 

Это код, я увидел avaluating числа Фибоначчей с помощью запоминания, что это [0,1]+[-1]*(n-1) значит? Не могли бы вы объяснить мне, что представляет собой этот тип письма?

Answer 1

[0, 1] + [-1] * (n - 1) означает «сцепить два списка, один [0, 1], другой является -1 повторил n-1 раз».

Answer 2

Странное кодирование. Похоже на синтаксические ошибки. Но в соответствии с вашим вопросом:

[0,1] представляет собой список с двумя элементами, первый представляет собой целое число 0, а второй один является целым числом 1.

Разумной реализация такой функции с запоминанием в Python будет:

def fib(i): 
    try: 
     return fib._memory[i] 
    except KeyError: 
     pass 
    if i == 1 or i == 2: 
     return 1 
    else: 
     f = fib(i-1) + fib(i-2) 
     fib._memory[i] = f 
     return f 
fib._memory = {} 

Answer 3

[-1] * 5 будет создавать новый список с пятью элементами которого являются -1, т.е. [-1 -1 -1 -1 -1]

[0 1 ] + [- 1] * 5 добавит два списка, которые станут [0 1 -1 -1 -1 -1 -1]

Answer 4

Во-первых, я должен сказать, что даже после редактирования ваш код по-прежнему имеет неправильный отступ: return mem[i] не должен быть без изменений.

Среди операций списка «+» означает конкатенацию, «*» означает повторение, поэтому [0,1]+[-1]*(n-1) означает список: [0, 1, -1, ..., -1] (полностью (n-1) отрицательный 1).

Больше объяснения:

Список [0, 1, -1, ..., -1] магазины, рассчитанные последовательности Фибоначчи (запоминанием). Первоначально он содержит только два допустимых значения: 0 и 1, все элементы «-1» означают, что последовательность в этом индексе еще не была вычислена. Эта записка передается как второй параметр для функции fib_mem_helper. Если номер фибоначчи указанного индекса (например, i) не был вычислен (если у mem[i] == -1), fib_mem_helper рекурсивно вычислит его и сохранит его до mem[i]. Если он был вычислен, просто вернитесь из записки, не переучивая.

Вот и вся история.

Заключительное слово:

Этот код не достаточно эффективно, хотя это требует использования запоминания. Фактически, он создает новый список каждый раз, когда вызывается fib_mem. Например, если вы дважды вызываете fib_mem(8), второй вызов по-прежнему должен воссоздать список и повторно пересчитать все заново. Причина в том, что вы храните записку внутри с объемом fib_mem. Чтобы исправить это, вы можете сохранить памятку в виде словаря, который находится за пределами fib_mem.

Answer 5

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

mem = {0:0, 1:1} 

def fib(n): 
    global mem 
    if mem.get(n,-1) == -1: 
     mem[n] = fib(n-1) + fib(n-2) 
    return mem[n] 

Делая mem глобальную переменную, вы можете воспользоваться запоминанием по призывам fib(). Строка mem.get(n,-1) == -1 проверяет, содержит ли mem расчет для n. Если это так, он возвращает результат mem[n]. В противном случае он рекурсивно звонит fib() для вычисления fib(n) и сохраняет это в mem[n].

---

Давайте рассмотрим ваш код. Второй аргумент здесь fib_mem_helper(n,[0,1]+[-1]*(n-1)) передает список формы [0,1, -1, -1, ...] с длиной (n+1). В функции fib_mem_helper этот список ссылается на переменную mem. Если mem[i] окажется равным -1, вы вычисляете m[i]; в противном случае используйте уже вычисленный результат для mem[i]. Поскольку вы не сохраняете mem по звонкам до fib_mem(), он будет работать на порядок медленнее.

Answer 6

Ускорение в python может быть в миллион раз или более при использовании memoization для определенных функций. Вот пример с рядом фибоначчи. Обычный рекурсивный способ подобен этому и берет навсегда.

def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50), 

Тот же алгоритм с памятью занимает несколько миллисекунд. Попробуй сам!

def memoize(f): 
    memo={} 
    def helper(x): 
     if x not in memo: 
      memo[x]=f(x) 
     return memo[x] 
    return helper 

@memoize 
def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50),