Если вы когда-либо сталкивались с тем, что практиковались в рекурсии, я совершенно уверен, что вы сталкивались с алгоритмом последовательности Фибоначчи. Если вы не знакомы с этой проблемой, взгляните на то, что о ней говорит Википедия:
В математике числа Фибоначчи, обычно обозначаемые как Fn, образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число представляет собой сумму двух предшествующие.
Итак, если мы начнем с 0 и 1, вот как будут выглядеть первые N чисел Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Как видите, каждое число (кроме первых двух) получается из суммы двух предыдущих. Например, 13является результатом сложения8и 5.
В этой статье мы разработаем решение на Javascript с использованием рекурсии и улучшим его производительность с помощью замыканий.
Первое решение
Давайте попробуем написать функцию, которая будет получать число n и извлекать число Фибоначчи в позиции n. Мы будем использовать рекурсивный подход:
function fibonacci(n) {
if (n <= 0) {
return 0;
} else if (n <= 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
(Обратите внимание, что некоторые теории пропускают первый 0 из последовательности Фибоначчи, и в этом случае все, что вам нужно сделать, это опустить первый оператор if и изменить второй на n ‹ 2 )
Довольно просто, да? Давайте создадим несколько тестовых случаев:
console.log(fibonacci(0)); // 0 console.log(fibonacci(1)); // 1 console.log(fibonacci(2)); // 1 console.log(fibonacci(3)); // 2 console.log(fibonacci(4)); // 3 console.log(fibonacci(10)); // 55 console.log(fibonacci(20)); // 6765 console.log(fibonacci(30)); // 832040 console.log(fibonacci(40)); // 102334155
Это здорово! Теперь, если вы выполните это в своем браузере, вы увидите, что он становится все медленнее и медленнее по мере увеличения параметра n. Это связано с тем, что при каждом вызове fibonacci выполняется еще 2 вызова одной и той же функции (за исключением случаев, когда n ≤ 2). Это называется экспоненциальной сложностью и обозначается O(2^n).
Как мы можем уменьшить эту сложность, не удаляя рекурсию? Чтобы проверить это, мы сначала создадим базовый бенчмаркинг, используя нашего старого друга console.log.
Бенчмаркинг
Давайте остановимся на этом решении и добавим журналирование, чтобы увидеть, сколько раз наша функция выполнялась:
let timesExecuted = 0;
function fibonacci(n) {
timesExecuted++;
if (n <= 0) {
return 0;
} else if (n <= 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 204668309
Можете ли вы что-то заметить? Для такого небольшого числа, как 40, мы получили более 200 миллионов выполнений, что невозможно масштабировать, и для обработки больших чисел потребуется огромный процессор.
Как мы можем улучшить это? Давайте взглянем на наш пример и посмотрим, что происходит внутри, и попробуем найти часть, которую можно сделать более эффективно.
------------------ fibonacci(40) ------------------ timesExecuted = 1 fibonacci(39) fibonacci(38) ------------------ ------------------ fibonacci(39) ------------------ timesExecuted = 2 fibonacci(38) fibonacci(37) ------------------ ------------------ fibonacci(38) ------------------ timesExecuted = 3 fibonacci(37) fibonacci(36) ------------------ ...
Вы можете заметить, что операторы, отмеченные полужирным, будут выполняться более одного раза, и это вызовет множество ненужных вызовов, которые мы можем каким-то образом избежать, сохраняя эти результаты где-то. Что мы можем использовать?
Мемоизация
Есть способ, которым мы можем использовать замыкания для хранения результатов некоторых из этих выполнений и избежать их повторной обработки позже. Для этого мы можем использовать мемоизацию:
Техника оптимизации, используемая в первую очередь для ускорения компьютерных программ за счет сохранения результатов дорогостоящих вызовов функций.
По сути, прежде чем использовать рекурсию для получения n-го числа Фибоначчи, мы будем искать в памяти, чтобы увидеть, было ли это значение вычислено ранее, а затем использовать его, как кеш.
Теперь мы немного изменим наш код, чтобы он поддерживал это:
let timesExecuted = 0;
function fibonacci(n) {
const innerFibonacci = m => {
timesExecuted++;
if (m <= 0) {
return 0;
} else if (m <= 2) {
return 1;
} else {
return innerFibonacci(m - 2) + innerFibonacci(m - 1);
}
}
return innerFibonacci(n);
}
const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 204668309
Как видите, теперь мы определили функцию innerFibonacci, которая будет отвечать за вычисление значения, и теперь у нас есть оболочка с именем fibonacci, которая является функцией, которая будет выполняться изначально и которая вернет наш результат.
При этом следующим шагом будет создание переменной хранения внутри нашей функции-оболочки для хранения наших частичных результатов и проверки наличия ранее вычисленного значения перед вычислением новых значений.
Вот как это будет выглядеть:
let timesExecuted = 0;
function fibonacci(n) {
const fibonacciCache = new Map();
const innerFibonacci = m => {
if (fibonacciCache.has(m)) {
return fibonacciCache.get(m);
} else if (m <= 0) {
timesExecuted++;
return 0;
} else if (m <= 2) {
timesExecuted++;
return 1;
} else {
const resultInner = innerFibonacci(m - 2) + innerFibonacci(m - 1);
timesExecuted++;
fibonacciCache.set(m, resultInner);
return resultInner;
}
}
return innerFibonacci(n);
}
const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 41
Ты можешь в это поверить? 41 раз против 200 миллионов раз, это невероятно. Мы используем Map javascript для хранения наших данных, но вы можете использовать собственный Object, если хотите, или любую другую структуру данных, которая вам нравится больше всего. Тем не менее, есть возможности для улучшения. Мы можем попытаться удалить timesExecuted++ и несколько если, чтобы избежать повторения, и мы можем немного лучше сортировать вещи.
Давайте попробуем это сделать:
function fibonacci(n) {
const fibonacciCache = new Map();
// Predefined values
fibonacciCache.set(0, 0);
fibonacciCache.set(1, 1);
fibonacciCache.set(2, 1);
const innerFibonacci = m => {
if (fibonacciCache.has(m)) {
return fibonacciCache.get(m);
} else {
const resultInner = innerFibonacci(m - 1) + innerFibonacci(m - 2);
timesExecuted++;
fibonacciCache.set(m, resultInner);
return resultInner;
}
}
return innerFibonacci(n);
}
const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 38
С этим новым изменением мы определяем некоторые значения в нашем кеше мемоизации, чтобы мы могли удалить некоторые операторы if, а также мы сокращаем количество выполнений с 41 до 38. Легко!
Вывод
Несмотря на то, что это не лучшее решение для алгоритма Фибоначчи, изучение рекурсии и ее осложнений может оказаться полезным. Кроме того, с этой реализацией вы можете получить немного больше знаний о мемоизации и о том, как она может помочь вам повысить производительность ваших приложений.
Как вы думаете, есть ли способ еще больше сократить количество выполнений с помощью этой реализации? Что бы вы изменили, чтобы сделать его еще более эффективным?
