Як використовувати 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])
  • @memoizeДекоратори ES7 від 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.