Если вы не можете произнести это правильно, продолжайте читать дальше, чтобы понять, что это такое. Мемоизация - отличный инструмент для улучшения времени выполнения больших сложных приложений путем сохранения или кэширования предыдущих результатов, чтобы их можно было вызвать, если алгоритм снова будет запущен с тем же inout. Он может превратить очень сложные функции в очень эффективные, и это умение, о котором программисты должны знать.
Чтобы увидеть, как мемоизация вступает в игру, рассмотрим следующую функцию JavaScript, которая принимает число и возводит его в квадрат:
function square(n) {
let result = 0
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
result +=1
}
}
return result
}
Хорошо, первое, что вы можете заметить, это то, что эта функция невероятно неэффективна. Это только для примера. Эта функция займет много времени, когда мы начнем вводить большие числа, это время выполнения может составлять всего полсекунды или около того, но в стандартах программирования это время начинает складываться. Особенно когда вы думаете о тех гигантских программных приложениях, которые существуют там. Также подумайте, приходилось ли нам вызывать эту функцию несколько раз с одним и тем же большим вводом. Все больше и больше времени работы.
Здесь мы можем использовать мемоизацию для кэширования предыдущих результатов. Таким образом, если эта функция была запущена с тем же вводом, что и раньше, мы можем мгновенно получить результаты. Чтобы использовать мемоизацию, мы можем настроить нашу функцию, включив в нее следующее:
const previousResults = []
function square(n) {
let result = 0
for (let i = 1; i < n; i++ {
for (let j = 1; j < n; j++ {
result +=1
}
}
previousResults[n] = result
return result
}
Мы начинаем с создания массива для хранения всех предыдущих результатов, чтобы каждый раз, когда мы запускаем эту функцию, значение «результата» сохранялось в массиве. Прямо сейчас время выполнения для нескольких вызовов все еще будет очень медленным, мы сначала должны проверить, вызывалась ли эта функция раньше с тем же предыдущим вводом:
const previousResults = []
function square(n) {
if (previousResults[n] != null) {
return previousValues[n]
}
let result = 0
for (let i = 1; i < n; i++ {
for (let j = 1; j < n; j++ {
result +=1
}
}
previousResults[n] = result
return result
}
Этот открывающий оператор if является ключом к тому, чтобы мемоизация работала. Мы проверяем массив, чтобы увидеть, есть ли уже результат предыдущего вызова функции, и если он есть, просто возвращаемся вместо запуска всей функции.
Это отличный пример использования мемоизации, но, как указывалось ранее, функция была неэффективной с самого начала, поэтому давайте взглянем на другой пример.
Мемоизация очень хорошо работает с рекурсивными функциями, когда функция вызывает себя до тех пор, пока не будет выполнено определенное условие. Если функция вызывает сама себя, возможность сохранить предыдущие результаты поможет улучшить сложность. Давайте посмотрим на последовательность Фибоначчи, где следующее число - это сумма двух предыдущих чисел.
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]
Если бы мы хотели создать рекурсивную функцию для определения n-го числа последовательности, это могло бы выглядеть примерно так:
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) fib(n - 2)
}
Теперь это неэффективно, но не намеренно, это займет все больше времени, поскольку значение ’n’ увеличивается. Вы могли заметить, что в вызывающей себя функции мы будем производить вычисления, используя аналогичные входные данные. Мы можем использовать мемоизацию, чтобы ускорить этот процесс, на этот раз я запомню с помощью отдельной функции:
function memoize(fn) {
previousValues = {}
return function(...args) {
if (previousValues[args] {
return previousValues[args]
}
const result = fn.apply(this)
previousValues[args] = result
return result
}
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) fib(n - 2)
}
fib = memoize(fib)
Это немного более общий подход к мемоизации, но здесь применимы те же концепции. Как только мы запустим функцию fib. Наш результат будет где-то сохранен, в данном случае это объект, показанный выше. Первое, что происходит, - мы проверяем объект, чтобы увидеть, есть ли там что-нибудь, и, если да, возвращаем его. Только когда функция увидит, что она не была запущена с новым вводом, она будет запущена полностью, но тогда результат будет сохранен для следующего раза.
Мемоизация может быть труднопроизносимой, но она чрезвычайно полезна при динамическом программировании и сложных алгоритмах. Это инструмент, о котором программисты должны знать, чтобы создавать приложения или просто готовиться к следующему техническому собеседованию!
