Хорошо, приготовься к настоящей кроличьей норе моей ночи вторника….
Сначала JP привел меня к мемоизации, которая затем привела меня к рекурсии, которая привела к последовательностям Фибоначчи, которые, очевидно и неизбежно привели меня к кроликам ...
Предупреждаю ...
Последовательность Фибоначчи
Что такое последовательность Фибоначчи? Это серия чисел, в которой каждое число представляет собой сумму двух предыдущих чисел.
Это очень известный набор чисел, который был обнаружен в 12 веке математиком Леонардо Фибоначчи. Эта последовательность была впервые задумана, когда Фибоначчи размышлял над вопросом воспроизводства кроликов? Странный / случайный, я знаю. Оставайся со мной.
В основном проблема предполагает следующие условия:
- Начните с одного кролика-самца и только что родившихся кроликов-самок.
- Кролики достигают половой зрелости через месяц.
- Срок беременности кролика - один месяц.
- Достигнув половой зрелости, кролики-самки рожают ежемесячно.
- От кролика-самки рождаются кролики-самцы и кролики-самки.
- Кролики не умирают.
Примечание - Спираль Фибоначчи
Спираль Фибоначчи представляет собой серию соединенных четверть окружностей, нарисованных внутри массива квадратов с числами Фибоначчи для измерений. Квадраты идеально подходят друг к другу из-за характера последовательности, где следующее число равно сумме двух перед ним. Любые два последовательных числа Фибоначчи имеют отношение, очень близкое к золотому сечению, которое составляет примерно 1,618034. Чем больше пара чисел Фибоначчи, тем ближе приближение. Спираль и получившийся прямоугольник известны как золотой прямоугольник. Последовательность также тесно связана с известным числом, называемым золотым сечением . Вы можете найти эту последовательность чисел в витках естественных спиралей, в растениях и в генеалогическом древе пчел.
Рекурсия
Хорошо, вернемся к тому, как все это связано с кодом. Итак, мы все слышали, как люди говорят о рекурсии и о том, что именно тогда функция вызывает сама себя и делает программы более эффективными. Но почему? И как? И когда бы вы это использовали? Давайте окунемся в наш пример, используя последовательность Фибоначчи!
Ниже приведен пример расчета данного индекса последовательности Фибоначчи. Обратите внимание, что он вызывает последовательность Фибоначчи для себя, пока не дойдет до базового случая ряда, так как каждое продолжающееся число зависит от предшествующих, а затем вычисляет обратно до желаемого индекса.
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}Эта функция хорошо работает при малых значениях «n». Однако производительность быстро ухудшается по экспоненте с увеличением «n». Это потому, что два рекурсивных вызова повторяют одну и ту же работу. Вы можете увидеть эти повторяющиеся вызовы в дереве рекурсии ниже.
Вы можете видеть, что F (1) вычисляется трижды, F (2) 5 раз, F (3) 3 раза, F (4) дважды….…
На очереди Memoization….
Воспоминание
Идея мемоизации заключается в том, что это метод программирования, который пытается повысить производительность функции путем кэширования ранее вычисленных результатов. По сути, каждый раз, когда рассчитывается индекс Фибоначчи, результат может быть сохранен во внешнем объекте, чтобы рекурсивная функция могла получить к нему доступ и использовать уже рассчитанный результат в своих будущих вычислениях, поскольку все они зависят друг от друга.
Боковое примечание: определение кеша - это «временное хранилище или память, обеспечивающая быстрый доступ к данным». Одно заблуждение, хотя и в основном с моей стороны, заключается в том, что кеширование осуществляется только через браузер и в виде таких вещей, как файлы cookie, токены и т. д. Однако этот термин относится ко всему в вычислительной технике, где что-то сохраняется для дальнейшего использования. для ускорения обработки.
«Мемоизированные функции хранят кеш, который индексируется их входными аргументами. Если аргументы существуют в кеше, возвращается кешированное значение. В противном случае функция выполняется, и новое вычисленное значение добавляется в кэш ».
Давайте взглянем на приведенный ниже код и заметим, что мы сохраняем рассчитанные результаты в памятке.
- Он устанавливает свой объект кеширования memo.
- Сначала он проверяет, был ли ранее рассчитан индекс Фибоначчи и сохранен ли он в памятке.
- Если это так, то он использует это значение в рекурсивной функции.
- Если это не так, он продолжает вычислять следующий член в последовательности Фибоначчи, как и раньше, одновременно сохраняя его в объекте кэша для использования в будущем.
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();Этот код позволяет функции ссылаться на ранее рассчитанные значения. Давайте вернемся к нашему дереву рекурсии, но с мемоизацией. Как видите, теперь мы можем исключить многие из наших расчетов.
Это магия мемоизации!
К сожалению, большинство задач более сложные, и функции имеют более одного аргумента. Это означает, что не существует простой пары «ключ-значение» для хранения каждого вычисления. С этим можно справиться двумя способами. Наиболее распространенным является создание иерархии объектов (например, вложенного хеша). Менее распространенным является единственный объект кеша, который индексируется комбинацией всех аргументов функции. При таком подходе аргументы преобразуются в массив, а затем используются для индексации кеша. Оба эти метода подробно описаны в последнем ресурсе ниже. Посмотри!
Таким образом, мемоизация полезна, когда рекурсивная функция повторяет несколько вычислений, потому что она может сохранять эти результаты в объекте и извлекать их, когда это необходимо, вместо того, чтобы полностью их пересчитывать. Если это короткая функция, которая используется не часто, а время вычислений невелико, то мемоизация может не понадобиться.
Ресурсы:
