Как да използвате Memoize, за да кеширате резултатите от функцията на JavaScript и да ускорите кода си

Функциите са неразделна част от програмирането. Те помагат да се добави модулност и повторна употреба към нашия код.

Доста често се разделя нашата програма на парчета, като се използват функции, които можем да извикаме по-късно, за да извършим някакво полезно действие.

Понякога функция може да стане скъпа за извикване няколко пъти (да речем, функция за изчисляване на факториал на число). Но има начин да оптимизираме такива функции и да ги накараме да се изпълняват много по-бързо: кеширане .

Например, да предположим, че трябва functionда върнем факториала на число:

function factorial(n) { // Calculations: n * (n-1) * (n-2) * ... (2) * (1) return factorial }

Чудесно, сега да намерим factorial(50). Компютърът ще извърши изчисления и ще ни върне окончателния отговор, сладко!

Когато това стане, нека да намерим factorial(51). Компютърът отново извършва редица изчисления и ни дава резултата, но може би сте забелязали, че вече повтаряме редица стъпки, които биха могли да бъдат избегнати. Оптимизиран начин би бил:

factorial(51) = factorial(50) * 51

Но ние functionизвършваме изчисленията от нулата всеки път, когато се извика:

factorial(51) = 51 * 50 * 49 * ... * 2 * 1

Не би ли било готино, ако някак си нашата factorialфункция можеше да запомни стойностите от предишните си изчисления и да ги използва, за да ускори изпълнението?

Идва запомнянето , начин functionда запомним (кешираме) резултатите. След като вече разбирате основно какво се опитваме да постигнем, ето официално определение:

Мемоизирането е техника за оптимизация, използвана предимно за ускоряване на компютърните програми чрез съхраняване на резултатите от скъпи извиквания на функции и връщане на кеширания резултат, когато се появят едни и същи входове

Запомнянето с прости думи означава запаметяване или съхраняване в паметта. Функцията за запомняне обикновено е по-бърза, защото ако функцията бъде извикана впоследствие с предишната (ите) стойност (и), вместо да изпълняваме функцията, ще извличаме резултата от кеша.

Ето как може да изглежда една проста запомнена функция (и ето CodePen, в случай че искате да взаимодействате с нея) :

// a simple function to add something const add = (n) => (n + 10); add(9); // a simple memoized function to add something const memoizedAdd = () => { let cache = {}; return (n) => { if (n in cache) { console.log('Fetching from cache'); return cache[n]; } else { console.log('Calculating result'); let result = n + 10; cache[n] = result; return result; } } } // returned function from memoizedAdd const newAdd = memoizedAdd(); console.log(newAdd(9)); // calculated console.log(newAdd(9)); // cached

Вземане на мемоизация

Някои изводи от горния код са:

  • memoizedAddвръща a, functionкоето се извиква по-късно. Това е възможно, тъй като в JavaScript функциите са първокласни обекти, което ни позволява да ги използваме като функции от по-висок ред и да върнем друга функция.
  • cacheможе да запомни неговите стойности, тъй като върнатата функция има затваряне над нея.
  • От съществено значение е запомнената функция да е чиста. Чистата функция ще върне същия изход за конкретен вход, без значение колко пъти е извикан, което прави cacheработата според очакванията.

Писане на собствена memoizeфункция

Предишният код работи добре, но какво, ако искаме да превърнем която и да е функция в запомнена функция?

Ето как да напишете собствената си функция за запомняне (codepen):

// a simple pure function to get a value adding 10 const add = (n) => (n + 10); console.log('Simple call', add(3)); // a simple memoize function that takes in a function // and returns a memoized function const memoize = (fn) => { let cache = {}; return (...args) => { let n = args[0]; // just taking one argument here if (n in cache) { console.log('Fetching from cache'); return cache[n]; } else { console.log('Calculating result'); let result = fn(n); cache[n] = result; return result; } } } // creating a memoized function for the 'add' pure function const memoizedAdd = memoize(add); console.log(memoizedAdd(3)); // calculated console.log(memoizedAdd(3)); // cached console.log(memoizedAdd(4)); // calculated console.log(memoizedAdd(4)); // cached

Сега това е страхотно! Тази проста memoizeфункция ще обгърне всяко просто functionв запомнен еквивалент. Кодът работи добре за прости функции и може лесно да бъде променен, за да се справи с произволен брой argumentsспоред вашите нужди. Друга алтернатива е да се използват някои фактически библиотеки като:

  • На Лодаш _.memoize(func, [resolver])
  • ES7 @memoizeдекоратори от decko

Запаметяване на рекурсивни функции

Ако се опитате да предадете рекурсивна функция на memoizeфункцията по-горе или _.memoizeот Lodash, резултатите няма да бъдат както се очаква, тъй като рекурсивната функция при следващите си повиквания в крайна сметка ще извика себе си вместо запомнената функция, като по този начин не използва cache.

Просто се уверете, че вашата рекурсивна функция извиква запомнената функция. Ето как можете да промените пример за факториал на учебник (codepen):

// same memoize function from before const memoize = (fn) => { let cache = {}; return (...args) => { let n = args[0]; if (n in cache) { console.log('Fetching from cache', n); return cache[n]; } else { console.log('Calculating result', n); let result = fn(n); cache[n] = result; return result; } } } const factorial = memoize( (x) => { if (x === 0) { return 1; } else { return x * factorial(x - 1); } } ); console.log(factorial(5)); // calculated console.log(factorial(6)); // calculated for 6 and cached for 5

Няколко точки за отбелязване от този код:

  • Най- factorialфункцията се рекурсивно извикване на memoized версия на себе си.
  • Функцията за запомняне кешира стойностите на предишни факториали, което значително подобрява изчисленията, тъй като те могат да бъдат използвани повторно factorial(6) = 6 * factorial(5)

Съхранението на паметта същото ли е като кеширането?

Да, нещо като. Мемоизирането всъщност е специфичен тип кеширане. Докато кеширането може да се отнася най-общо до всяка техника на съхранение (като HTTP кеширане) за бъдеща употреба, запомнянето специално включва кеширане на връщаните стойности на a function.

Кога да запомните функциите си

Въпреки че може да изглежда, че запомнянето може да се използва с всички функции, всъщност има ограничени случаи на употреба:

  • За да запомните функция, тя трябва да бъде чиста, така че връщаните стойности да са едни и същи за едни и същи входове всеки път
  • Запомнянето е компромис между добавеното пространство и добавената скорост и по този начин е важно само за функции с ограничен входен обхват, така че кешираните стойности могат да се използват по-често
  • Може да изглежда, че трябва да запомните извикванията на API, но не е необходимо, защото браузърът автоматично ги кешира вместо вас. Вижте HTTP кеширане за повече подробности
  • Най-добрият случай на употреба, който открих за запомнени функции, е за тежки изчислителни функции, които могат значително да подобрят производителността (факториал и фибоначи не са наистина добри примери от реалния свят)
  • Ако сте в React / Redux, можете да проверите повторно избиране, което използва запомнен селектор, за да гарантира, че изчисленията се извършват само когато се случи промяна в свързана част от дървото на състоянието.

Допълнителна информация

The following links can be useful if you would like to know more about some of the topics from this article in more detail:

  • Higher order functions in JavaScript
  • Closures in JavaScript
  • Pure functions
  • Lodash’s _.memoize docs and source code
  • More memoization examples here and here
  • reactjs/reselect

I hope this article was useful for you, and you’ve gained a better understanding of memoization in JavaScript :)

You may follow me on twitter for latest updates. I've also started posting more recent posts on my personal blog.