Сегодняшний технический блог посвящен функции Фибоначчи. У меня не было этого в моих технических интервью, но, насколько я понимаю, это общий вопрос. Если временная сложность вашего рекурсивного решения Фибоначчи экспоненциальна, метод сокращения времени, необходимого для запуска этой функции, заключается в использовании мемоизации (это один из способов сделать это).
Оригинальное решение работает медленно из-за повторяющихся вызовов функции Фибоначчи с одинаковыми аргументами.
Функция мемоизации сохраняет аргументы и результаты каждого вызова функции и возвращает предварительно вычисленные результаты. Мы будем извлекать результат из нашего пространства в памяти вместо того, чтобы каждый раз запускать функцию.
Мы объявим функцию и передадим другую функцию fn в качестве аргумента, чтобы ускорить нашу исходную функцию. Мы объявим кеш — объект, который будет хранить наши аргументы с соответствующими результатами. Мы возвращаем нашу функцию с количеством аргументов, с которыми эта функция будет вызываться с помощью … args. Мы рассмотрим объект и его ключи и вернем cache[args], если он существует. Если эта функция с этими конкретными аргументами была вызвана ранее — вернуть ее с результатами, хранящимися в объекте кеша. В противном случае мы вызовем эту функцию с новыми аргументами и кэшируем результаты внутри объекта кеша. Константный результат настроен на вызов нашей исходной функции fn, и мы используем вспомогательную функцию и сохраняем результат в объекте кеша. Наконец, мы возвращаем результат.
функция запоминания (fn) {
константный кеш = {};
функция возврата (…аргументы) {
если (кэш [аргументы]) {
вернуть кеш [аргументы];
}
константный результат = fn.apply(это, аргументы);
кеш[аргументы] = результат;
вернуть результат;
};
}
Я узнал об этом от Стивена Грайдера, который так хорошо все объяснил. Я полагаю, ничто не является ракетостроением, только ракетостроение. Удачного кодирования!
