Ваш процесс запоминания неисправен!
Вы не возвращаете объекты с одинаковой формой
Когда вы не находите сотрудника в кеше, тогда Вы ищите его и возвращаете весь объект, однако вы запоминаете только часть объекта:
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
Итак, когда вы находите сотрудника в кеше, вы возвращаете нижняя версия данных:
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache);//name
Вы получаете разные данные назад при вызове одной и той же функции с одинаковыми параметрами.
Вы не возвращаете одни и те же объекты
Еще одна большая проблема заключается в том, что вы создаете новый объект - даже если вы измените, чтобы получить полную копию, памятка не будет прозрачной:
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
memoizedEmployee(1)
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache); //id + name
console.log("found === fromCache :", found === fromCache); // false
Результат в основном один и тот же, вы получаете «разные» данные в том смысле, что объекты не совпадают. Так, например, если вы делаете:
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const original = employees[0];
const found = memoizedEmployee(1);
found.foo = "hello";
console.log("found:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + bar
console.log("original:", original); //id + name + foo
Сравните с обычной реализацией
Я буду использовать memoize от Loda sh, но есть много других обобщений c реализации, и они все еще работают одинаково, так что это только для справки:
const { memoize } = _;
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
const memoizedEmployee = memoize(findEditedByEmployee);
const original = employees[0];
const found = memoizedEmployee(1);
console.log("found 1:", found); //id + name
found.foo = "hello";
console.log("found 2:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name + foo
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + foo + bar
console.log("original:", original); //id + name + foo + bar
console.log("found === fromCache :", found === fromCache); //true
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
Просто демонстрация того, что памятка полностью прозрачна и не вызывает каких-либо странных или необычных действий. Использование запомненной функции в точности аналогично обычной функции с точки зрения эффектов. Единственная разница заключается в кешировании, но оно не влияет на поведение функции.
На актуальные вопросы:
Как выполнить тест, чтобы увидеть, какой из этих двух прогонов самый быстрый?
Честно, а лично - не стоит. Правильная реализация памятки обладает известными свойствами. Линейный поиск также обладает известными свойствами. Итак, тестирование на скорость - это тестирование двух известных свойств обоих алгоритмов.
Давайте окунемся здесь в чистую логику c - нам нужно рассмотреть две вещи:
- реализация верна (назовем это P )
- свойства реализации верны (назовем это Q )
Мы можем определенно сказать, что "Если реализация верна , то свойства реализации верны", преобразуются в" если P , то Q"или формально P -> Q. Если бы мы go в противоположном направлении Q -> P и попытались проверить известные свойства, чтобы убедиться, что реализация верна, тогда мы совершаем ошибку , подтверждая последующее .
Мы действительно можем заметить, что тестирование скорости - это даже не проверка правильности решения. Вы можете иметь неправильную реализацию памятки, но она будет показывать то же свойство скорости, что и O(n) поиск один раз и O(1) при повторных чтениях, как правильная памятка. Итак, тест Q -> P не пройдёт.
Вместо этого вам следует проверить правильность реализации , если вы можете доказать это, то можете сделать вывод, что при повторных чтениях вы будете иметь постоянную скорость. И O(1) доступ будет (в большинстве случаев, особенно в этом) быстрее, чем O(n) поиск.
Следовательно, если вам не нужно доказать правильность, тогда вы можете принять остальное как должное. А если вы используете известную реализацию памятки, вам не нужно проверять свою библиотеку.
С учетом всего вышесказанного, - это , что вам, возможно, все же нужно знать. Кэширование при запоминании основано на создании правильного ключа для кэшируемого элемента. И это может потенциально иметь большие, даже если постоянные, накладные расходы в зависимости от того, как ключ получен. Так, например, поиск чего-то в начале массива может занять 10ms, но создание ключа для кэша может занять 15ms, что означает, что O(1) будет медленнее . Медленнее, чем в некоторых случаях.
Правильный тест для проверки скорости обычно состоит в проверке того, сколько времени (в среднем) требуется для поиска первого элемента в массиве, последнего элемента в массиве, чего-то из середины массива, затем проверьте, сколько времени требуется, чтобы извлечь что-то из кэша. Каждый из них должен быть запущен несколько раз, чтобы гарантировать, что вы не получите случайный скачок скорости ни вверх, ни вниз.
Но я бы сказал больше позже *
2) Это правильный способ использования заметок?
Да. Опять же, при условии правильной реализации, вот как вы это сделаете - запомните функцию, и тогда вы получите много преимуществ для кэширования.
С учетом вышесказанного вы можете видеть из реализации Loda sh, что вы можете просто обобщить реализацию памятки и применить ее к любой функции, вместо того, чтобы записывать запоминаемую версию каждой из них. Это довольно большое преимущество, поскольку вам нужно протестировать только одну функцию запоминания. Вместо этого, если у вас есть что-то вроде функций findEmployee(), findDepartment() и findAddress(), для которых вы хотите кэшировать результаты, то вам нужно протестировать каждую реализацию памятки.
3) Есть ли эмпирическое правило, когда использовать мемоизацию? Или я должен использовать его так часто, как могу?
Да, вы должны использовать его так часто, как можете * (с большой звездочкой)
* (огромной звездочкой)
Это самая большая звездочка, которую я знаю, как сделать, используя уценку (за исключением простого встраивания изображений). Я мог бы go немного больше, но увы.
Вы должны определить , когда вы можете использовать его, чтобы использовать его, когда можете. Я не просто говорю, что это сбивает с толку - вы не должны просто шлепать запомненные функции везде. В есть ситуации, когда вы не можете их использовать. И это то, на что я ссылался в конце ответа на первый вопрос - я хотел поговорить об этом в одном месте:
Вы должны очень осторожно наступить, чтобы проверить, что вы действительно используете является. Если у вас есть миллион элементов в массиве и только первые 10 ищутся быстрее, чем извлекаются из кэша, то 0,001% элементов не получили бы выгоды от кэширования. В таком случае - вы получаете выгоду от кеширования ... или нет? Если вы выполняете только пару операций чтения для каждого элемента и просматриваете менее четверти элементов, возможно, кэширование не принесет вам долгосрочной выгоды. И если вы просматриваете каждый элемент ровно два раза, то вы удваиваете ваше потребление памяти для честно довольно тривиального улучшения скорости в целом. Тем не менее, что, если вы не выполняете поиск в памяти из массива, а что-то вроде сетевого запроса (например, чтение из базы данных)? В этом случае кэширование даже для однократного использования может быть очень полезным.
Вы можете видеть, как одна деталь может сильно колебаться, следует ли вам использовать памятку или нет. И часто, даже когда вы изначально пишете приложение, это не совсем понятно, так как вы даже не знаете, как часто вы в конечном итоге вызываете функцию, какое значение вы ей дадите, и как часто вы ее вызываете с теми же значениями снова и снова. Даже если у вас есть представление о типичном использовании, вам все равно понадобится реальная среда для тестирования, вместо того, чтобы просто вызывать незарегистрированную и незарегистрированную версию функции в отдельности.
Eri c У Lippert есть удивительный пример тестирования производительности , который в основном сводится к - когда важна производительность, попытайтесь протестировать реальное приложение с реальными данными и реальным использованием. В противном случае ваш эталонный тест может быть отключен по разным причинам.
Даже если запоминание явно «быстрее», вы должны учитывать использование памяти. Вот немного глупый пример, чтобы проиллюстрировать запоминание, потребляющее больше памяти, чем необходимо:
const { memoize } = _;
//stupid recursive function that removes 1 from `b` and
//adds 1 to `a` until it finds the total sum of the two
function sum (a, b) {
if(b)
return sum(a + 1, b - 1)
//only log once to avoid spamming the logs but show if it's called or not
console.log("sum() finished");
return a;
}
//memoize the function
sum = memoize(sum);
const result = sum(1, 999);
console.log("result:", result);
const resultFromCache1 = sum(1, 999); //no logs as it's cached
console.log("resultFromCache1:", resultFromCache1);
const resultFromCache2 = sum(999, 1); //no logs as it's cached
console.log("resultFromCache2:", resultFromCache2);
const resultFromCache3 = sum(450, 550); //no logs as it's cached
console.log("resultFromCache3:", resultFromCache3);
const resultFromCache4 = sum(42, 958); //no logs as it's cached
console.log("resultFromCache4:", resultFromCache4);
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
Это поместит тысячу кэшированных результатов в память. Да, запомнившаяся функция глупа и выполняет много ненужных вызовов, а это значит, что у нее слишком много памяти. Однако в то же время, если мы повторно вызовем его с любыми аргументами, суммирующими до 1000 , то мы немедленно получим результат, не выполняя никакой рекурсии.
Вы можете легко иметь похожий реальный код, даже если рекурсия не задействована - может случиться так, что вы вызовете некоторую функцию много раз с большим количеством разных входных данных. Это заполнит кэш всеми результатами, и все же, будет ли это полезно или нет, все еще в воздухе.
Итак, если вы можете , вам следует использовать памятку. Самая большая проблема - узнать , если вы можете.