В этой статье мы узнаем, что такое мемоизация и как она была реализована внутри Redux Reselect.
Что такое мемоизация?
Мемоизация — это метод ускорения работы приложений за счет кэширования результатов ресурсоемких операций внутри функций и возврата кэшированных результатов с теми же входными данными, которые использовались повторно.
Как мы можем реализовать это с помощью VanillaJs и es5:
interface MemoizedFunction extends Function {
(param: any): any;
cache: {
[key: string]: any;
};
}
export const memoizationExample = function (param: any) {
// Checking is result already calculated for same entry
if (!memoizationExample.cache[param]) {
console.log('not cached');
const res = { data: param + 5 }; // Some heavy operations
// Adding calculated result to cache
memoizationExample.cache[param] = res;
}
console.log('outside');
return memoizationExample.cache[param];
} as MemoizedFunction;
memoizationExample.cache = {};
let resDef = memoizationExample(11); // First call calculating data
let resDef2 = memoizationExample(11); // Second call will get data from cache
console.log(resDef, resDef2, memoizationExample.cache);
// { data: 16 }, { data: 16 }, { "11": { "data": 16 } }
В JavaScript функции — это объекты, поэтому мы можем добавить свойство cache в memoizationExample и сохранить там кешированные данные. При первом вызове функции она проверит, есть ли в кеше уже сохраненный результат для этой записи. В случае, если кешированного результата нет, он войдет внутрь и выполнит некоторые тяжелые операции для получения данных и после того, как мы их сохраним. В случае, если уже есть кешированный результат, мы пропустим вычисления и просто вернем кешированные данные.
Использование карты и WeakMap
Объект Map содержит пары ключ-значение и запоминает исходный порядок вставки ключей. Любое значение (как объекты, так и примитивные значения) может быть использовано либо как ключ, либо как значение.
А WeakMap — это набор пар ключ/значение, ключи которого должны быть объектами, не создающими сильных ссылок на свои ключи. То есть наличие объекта в качестве ключа в WeakMap не препятствует сборке мусора.
let data = { value: 1 };
let map = new Map();
map.set(data, data);
data = null; // removing link to the object
// but object still saved inside `Map`,
// we can get it with map.keys()/map.values()
let weakData = { value: 1};
let weakMap = new WeakMap();
weakMap.set(weakData, weakData);
john = null; // removing link to the object
// And now when garbadge collector will be free will remove an object.
Таким образом, основное различие между этими двумя заключается в том, что в WeakMap вы можете использовать только объекты (также функции, поскольку они тоже являются объектами), а слабая карта не создает сильной ссылки, поэтому сборщик мусора может очистить неиспользуемые данные. Также WeakMap не имеет методов keys(), values().
Как мы можем реализовать мемоизацию с помощью Map/WeakMap
const cacheMap: Map<any, any> = new Map();
const cacheWeakMap: WeakMap<Object, any> = new WeakMap();
export const memoizationMap = (data: any) => {
// Checking is result already calculated for same entry
if(typeof data === 'object'){
if (!cacheWeakMap.has(data)) {
console.log('not cached WeakMap');
let res = data.value + 5; // Some heavy operations
// Adding calculated result to cache
cacheWeakMap.set(data, res);
}
console.log('outside WeakMap');
return cacheWeakMap.get(data);
} else {
if (!cacheMap.has(data)) {
console.log('not cached Map');
let res = data + 5; // Some heavy operations
// Adding calculated result to cache
cacheMap.set(data, res);
}
console.log('outside Map');
return cacheMap.get(data);
}
};
let data: number | null = 4;
let res1 = memoizationMap(data);
let res2 = memoizationMap(data); // data from cache
Итак, для объекта, который мы знаем, лучше использовать WeakMap для удаления неиспользуемых данных, а для других примитивов мы будем использовать Map.
Как мемоизация реализована внутри Reselect Redux(createSelector):
type EqualityType = (a: any, b: any) => boolean;
// Ussual compearing
export const defaultEqualityCheck: EqualityType = (a, b) => {
return a === b;
};
// Deep compearing arguments
function areArgumentsShallowlyEqual(equalityCheck: EqualityType, prev: any, next: any) {
// If either arguments is null, or if their lengths aren't the same, they aren't equal
if (prev === null || next === null || prev.length !== next.length) {
return false;
}
const length = prev.length;
for (let i = 0; i < length; i++) {
if (!equalityCheck(prev[i], next[i])) {
return false;
}
}
return true;
}
function createSelector(...funcs: any[]): (state: { numbers: number[]; strings: string[] }) => any {
let lastArgs: any = null;
let lastResult: any = null;
return function () {
// Checking is result already calculated for same entry
if (!areArgumentsShallowlyEqual(defaultEqualityCheck, lastArgs, arguments)) {
console.log('not cached selector');
const resultFunc = funcs.pop(); //This is the function that calculates the result
// Getting data fom selectors and paste data as props inside resultFunc
lastResult = resultFunc(...funcs.map(func => func.apply(null, arguments)));
lastArgs = arguments;
}
console.log('outside selector');
return lastResult;
};
}
// Usage
const stateStore: { numbers: number[]; strings: string[] } = {
numbers: [1, 2, 3, 4, 5],
strings: ['first', 'second', 'third', 'fourth', 'fifth'],
};
const getNumbers = (state: { numbers: number[] }) => state.numbers;
const getSum = createSelector(getNumbers, (numbers: any[]) => numbers.reduce((a, b) => a + b, 0));
console.log(getSum(stateStore));
console.log(getSum(stateStore)); // cache 15
Я реализовал упрощенную версию того, что есть у Reselect. Они используют defaultEqualityCheck и areArgumentsShallowlyEqual, чтобы узнать, были ли изменены аргументы. В случае отсутствия кеша они получают последний параметр из аргументов, который является resultFunc, он принимает сопоставление данных между селекторами с переданным Store в качестве аргументов.
Ссылка на повторный выбор мемоизации по умолчанию: https://github.com/reduxjs/reselect /blob/master/src/defaultMemoize.ts
Реализация с помощью WeakMap.
function createSelectorWeakMap(...funcs: any[]) {
let memoizedResults: WeakMap<any, any> = new WeakMap();
return function (...args: any[]) {
// Arg is array, so we need get obj as key into WeakMap which is out store
const argsKey = args[0];
if (memoizedResults.has(argsKey)) {
console.log('weak cache');
return memoizedResults.get(argsKey);
} else {
const resultFunc = funcs.pop();
const selectorsRes = funcs.map(func => {
// Check for several selectors
const selectors = Array.isArray(func) && func.map((item: Function) => item.apply(null, arguments));
return Array.isArray(func) ? selectors : func.apply(null, arguments);
});
// Check for several selectors to remove matrix
const isMatrix = Array.isArray(selectorsRes[0][0]) ? selectorsRes.flat() : selectorsRes;
// Blocking changing state with Object freeze
const result = resultFunc(...isMatrix.map(item => Object.freeze(item)));
memoizedResults.set(argsKey, result);
return result;
}
};
}
const getNumbersWeak = (state: { numbers: number[] }) => state.numbers;
const getStringsWeak = (state: { strings: string[] }) => state.strings;
const getSumWeak = createSelectorWeakMap([getNumbersWeak, getStringsWeak], (numbers: number[], strings: string[]) => {
console.log('number', Object.isFrozen(numbers), strings);
// numbers[1] = '2' Will give an error
return numbers.reduce(
(a, b, currentIndex) => {
return { sum: a.sum + b, str: a.str + strings[currentIndex] };
},
{ sum: 0, str: '' },
);
});
console.log('weak', getSumWeak(stateStore)); // calculates and logs 15
console.log('weak', getSumWeak(stateStore)); // returns memoized 15
Как мы знаем, метод Reselect createSelector всегда принимает функции-аргументы, поэтому лучше использовать WeakMap для очистки памяти с помощью сборщика мусора. В этой реализации я также добавил возможность указывать путь в виде массива к нескольким селекторам, чтобы получать от них данные, и Object.freeze(), чтобы предотвратить мутацию. Хранить данные.
Ссылка на мемоизацию WeakMap, там же добавили проверку на примитивы и использовали Map:
https://github.com/reduxjs/reselect/blob/master/src/weakMapMemoize.ts
Ссылка на повторное выделение createSelector: https://github.com/reduxjs/reselect/blob/master/src/index.ts#L80
Заключение
Меня очень интересовало общее поведение Memoization и то, как Reselect CreateSelector был реализован в Redux. Я надеюсь, что эта статья прольет свет на мемоизацию.
Если у вас есть какие-либо предложения, не стесняйтесь добавлять комментарии.
Исходный код: https://github.com/privalovbogdan/memoization-reselect
