Мемоизация рекурсивных выражений

313
21 июля 2017, 05:14

В книге Девида Фленегана в главе 8.8.4 Мемоизация есть пример кода и комментарий, на самом комментарии хотел бы остановиться ибо я не понял что автор имел ввиду. Для начала я вставлю код чтобы была понятна суть:

// Воз­вра­ща­ет ме­мои­зо­ван­ную вер­сию функ­ции f. Ра­бо­та­ет, толь­ко ес­ли все воз­мож­ные
// ар­гу­мен­ты f име­ют от­ли­чаю­щие­ся стро­ко­вые пред­став­ле­ния.
function memoize(f) {
 var cache = {}; // Кэш зна­че­ний со­хра­ня­ет­ся в за­мы­ка­нии.
 return function() {
 // Соз­дать стро­ко­вую вер­сию мас­си­ва arguments для ис­поль­зо­ва­ния
 // в ка­че­ст­ве клю­ча кэ­ша.
 var key = arguments.length + Array.prototype.join.call(arguments,",");
 if (key in cache) return cache[key];
 else return cache[key] = f.apply(this, arguments);
 };
}
// Воз­вра­ща­ет наи­боль­ший об­щий де­ли­тель двух це­лых чи­сел, ис­поль­зуя
// ал­го­ритм Эвк­ли­да: http://en.wikipedia.org/wiki/Euclidean_algorithm
function gcd(a,b) { // Про­вер­ка ти­пов a и b опу­ще­на
 var t; // Вре­мен­ная пе­ре­мен­ная для об­ме­на
 if (a < b) t=b, b=a, a=t; // Убе­дить­ся, что a >= b
 while(b != 0) t=b, b = a%b, a=t; // Это ал­го­ритм Эвк­ли­да по­ис­ка НОД
 return a;
}
var gcdmemo = memoize(gcd);
gcdmemo(85, 187) // => 17
// Об­ра­ти­те вни­ма­ние, что при ме­мои­за­ции ре­кур­сив­ных функ­ций же­ла­тель­но,
// что­бы ре­кур­сия вы­пол­ня­лась в ме­мои­зо­ван­ной вер­сии, а не в ори­ги­на­ле.
var factorial = memoize(function(n) {
 return (n <= 1) ? 1 : n * factorial(n-1);
 });
factorial(5) // => 120. Так­же по­мес­тит в кэш фак­то­риа­лы для чи­сел 4, 3, 2 и 1.

А теперь не понятный мне комментарий:

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

Что значит выполнение рекурсии в мемоизованной версии? И чем отличается от оригинала?

Answer 1

В исходном тексте написано более понятно.

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

var factorial = memoize(function(n) {
  return (n <= 1) ? 1 : n * factorial(n-1);
});
factorial(5); // => 120.
factorial(4); // посчитается мгновенно так как в кеше уже есть факториал для 4
factorial(6); // посчитается в одну операцию умножения 
              // так как в кеше уже есть факториал для 5
factorial(100); // считаться будет почти полностью
factorial(99);  // посчитается мгновенно - результат есть в кеше
READ ALSO
Как открыть DatePicker по клику на свой элемент?

Как открыть DatePicker по клику на свой элемент?

В данной библиотеке дейтпикер открывается по клику на инпутОднако хотелось бы привязать его к обычной кнопке

296
bootstrap select получить элемент

bootstrap select получить элемент

Есть библиотека Bootstrap selectнужно получить событие unselect - т е при снятии выделения нужно узнать на какой элемент был клик не получиться отловить...

282
NightmareJS cookies

NightmareJS cookies

В javascript не силен, был парсер на curl phpНо больше он уже для Яндекс Маркета не подходит

245
Соединить несколько картинок в canvas и загрузить

Соединить несколько картинок в canvas и загрузить

ТО картинка плохо отрисовывается то выскакивают ошибки по Cross-Origin и последняя ошибка Uncaught DOMException: Failed to execute 'toDataURL' on 'HTMLCanvasElement': Tainted canvases may not be exportedПодскажите...

401