Может ли кто-нибудь объяснить, что такое memoization?

Question

следующих статы статистика вызова функции Фибоначчи

Вот некоторые статистики, которые я получил после запуска профилировщика

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] 
    57358 function calls (68 primitive calls) in 0.211 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
    21 0.000 0.000 0.000 0.000 :0(append) 
    1 0.000 0.000 0.210 0.210 :0(exec) 
    20 0.000 0.000 0.000 0.000 :0(extend) 
    1 0.000 0.000 0.000 0.000 :0(print) 
    1 0.001 0.001 0.001 0.001 :0(setprofile) 
    1 0.000 0.000 0.210 0.210 <string>:1(<module>) 
21/1 0.000 0.000 0.210 0.210 Fibo1.py:12(fib_seq) 
57291/21 0.210 0.000 0.210 0.010 Fibo1.py:3(fib) 
    1 0.000 0.000 0.211 0.211 profile:0(print(fib_seq(20))) 
    0 0.000    0.000   profile:0(profiler) 

И после использования запоминания статистика профайлера

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] 
    147 function calls (89 primitive calls) in 0.002 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
    21 0.000 0.000 0.000 0.000 :0(append) 
    1 0.000 0.000 0.001 0.001 :0(exec) 
    20 0.000 0.000 0.000 0.000 :0(extend) 
    1 0.000 0.000 0.000 0.000 :0(print) 
    1 0.001 0.001 0.001 0.001 :0(setprofile) 
    1 0.000 0.000 0.001 0.001 <string>:1(<module>) 
    21 0.000 0.000 0.000 0.000 Fibo2.py:16(fib) 
21/1 0.000 0.000 0.001 0.001 Fibo2.py:26(fib_seq) 
59/21 0.000 0.000 0.000 0.000 Fibo2.py:9(__call__) 
    1 0.000 0.000 0.002 0.002 profile:0(print(fib_seq(20))) 
    0 0.000    0.000   profile:0(profiler) 

общие вызовы функций уменьшаются на большие числа. Если возможно p аренда предоставляет некоторые ссылки для получения более подробной информации о мемонации.

Answer 1

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

https://en.wikipedia.org/wiki/Memoization

В вашем случае, по-видимому (я предполагаю здесь, но пусть это ездить), каждый элемент в вашем массиве хранится в виде суммы. Без воспоминаний эти суммы вычисляются снова и снова. С memoization он падает один раз и никогда больше.

Answer 2

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