Фибоначчи

Перевод Как я посчитал миллионное число Фибоначчи

05.05.2021 20:22:59 |

Автор: admin

Все мы понимаем, что рекурсивное вычисление чисел Фибоначчи крайне неэффективно. Многим людям наверняка хотелось проверить, где пределы (не)эффективности, но не доходили руки, не хватало времени. Специально к старту нового потока курса Fullstack-разработчик на Python мы решили поделиться переводом статьи, автор которой шаг за шагом показывает возможности современного Python на примере разных подходов к вычислению чисел Фибоначчи. В статье вы найдёте проблемные значения n и сравнение производительности оптимального и неоптимального решений на графике.

Нет, заголовок вообще не кликбейтный. Несколько дней назад я действительно хотел найти оптимальное решение для расчёта чисел Фибоначчи, хотелось попробовать вычислить стотысячное число последовательности, но я задумался; если я могу вычислить стотысячное число, то что остановит меня в поисках миллионного числа Фибоначчи? Сегодня я покажу, как шёл к вычислению и с какими проблемами столкнулся.

Последовательность Фибоначчи одна из наиболее известных математических последовательностей и самый простой пример рекуррентных отношений. Каждое число последовательности это сумма двух предыдущих чисел, начиная с 0 и 1. Получается такая последовательность:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так далее...

В следующие несколько минут я исследую несколько разных подходов, а затем покажу оптимальное решение:

Простая рекурсия.
Кеш с рекурсией.
Итеративный метод.
Формула Бине.
Расчёт 1000000-го числа Фибоначчи.

Но, прежде чем мы начнём, я должен сказать, что все упомянутые тайминги касаются оборудования, на котором я работаю сейчас, а версия Python 3.9.1.

Простая рекурсия

Это очень простой способ получить N-ное число Фибоначчи на Python:

def recursiveFib(n):    if n == 1 or n == 2:        return 1    return recursiveFib(n - 1) + recursiveFib(n - 2)

В коде используется рекурсия, он вызывает сам себя несколько раз, вычисляя предыдущее число и используя это число для вычисления следующего. Но это также недостаток, поскольку функция чрезвычайно неэффективна и ресурсоёмка: на каждом этапе она вычисляет предыдущие 2 числа, а также предыдущие 2 числа этих чисел и т. д.

Вскоре вы достигаете точки, когда вычисление следующего числа занимает слишком много времени, например, на моём компьютере мне потребовалось 1,43 секунды, чтобы вычислить 35-е число. Очевидно, что вычисление более высоких значений будет чрезвычайно медленным и практически невозможным.

Кеш с рекурсией

Поскольку мы постоянно вычисляем предыдущие 2 числа, для хранения числа можно воспользоваться возможностями кеширования, не нужно будет вычислять числа несколько раз. Встроенный модуль functools позволяет нам работать с LRU кешем; этот тип кеша организует элементы в порядке их использования. Такой подход может значительно ускорить процесс.

from functools import lru_cache@lru_cache()def recursiveFibCached(n):    if n == 1 or n == 2:        return 1    return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)

Во-первых, нам нужно импортировать декоратор lru_cache из модуля functools и поместить его перед нашей функцией. Мы можем указать значение maxsize, чтобы сообщить кешу, сколько элементов нужно хранить, но по умолчанию оно равно 128, это значение прекрасно работает. Используя кеш, мы можем вычислить 200-е число Фибоначчи всего за 0,0002252 секунды!

Одна проблема с использованием рекурсии заключается в том, что если вы попытаетесь вычислить 501-е число, то получите ошибку RecursionError: maximum recursion depth exceeded in comparison. Но, к счастью, проблему можно решить, установив большее значение глубины рекурсии:

import syssys.setrecursionlimit(5000)

Теперь мы можем вычислить 1000-е число Фибоначчи, на вычисление которого мне потребовалось всего 0,001198 секунды. Однако это создало для меня ещё одну проблему: по какой-то странной причине я не мог вычислить 1553-е число в последовательности, и даже после увеличения предела рекурсии ничего не произойдёт, ничего не будет распечатано на терминале, и программа просто закончит выполнение. Очевидно, что это проблема и недостаток на моём пути к вычислению миллионного числа Фибоначчи.

Итеративный метод

Вы можете увидеть, что применение рекурсивного решения проблемы в компьютерной науке часто рассматривается как халатность, а итеративные методы считаются намного лучше. Для генерации чисел Фибоначчи мы можем создать итеративное решение:

def iterativeFib(n):    a, b = 0, 1    for i in range(n):        a, b = b, a + b    return a

Мы можем воспользоваться им, чтобы вычислить любое число Фибоначчи (я не тестировал подход с особенно большими числами), и часто этот подход работает также очень быстро, 1000-е число вычислилось всего за 0,0028195 секунды.

Вы можете задаться вопросом, почему нельзя воспользоваться этим подходом для вычисления 1000000-го числа, и да, это возможно, но займёт немного времени. Продолжайте читать, и я расскажу, почему.

Формула Бине

Формула Бине это формула, которая может использоваться для вычисления n-го члена последовательности Фибоначчи, а это именно то, что мы хотим сделать; эта формула названа в честь открывшего её французского математика Жака Филиппа Мари Бине. Вот она:

Формула Бине для вычисления n-ного числа Fibonacci

Вы можете заметить греческую букву PHI (), она означает золотое сечение:

Уравнение золотого сечения, phi

Можно написать формулу на Python и сразу же начать работать с ней:

def formulaFib(n):    root_5 = 5 ** 0.5    phi = ((1 + root_5) / 2)    a = ((phi ** n) - ((-phi) ** -n)) / root_5    return round(a)

Примечание: для реализации на Python нам нужно вернуть округление вычисляемого числа, потому что при вычислении большого числа Python вернёт результат, в котором может быть более двадцати девяток после запятой.

Всё это хорошо, так как теперь у нас нет никаких циклов и мы можем мгновенно вычислить ответ, верно? Что ж, в этом методе есть небольшая загвоздка. Если мы попытаемся вычислить что-либо выше 1475-го числа, то столкнёмся с ошибкой: OverflowError: (34, result too large). Это связано с тем, как в python реализованы числа с плавающей точкой, они могут иметь конкретное максимальное значение, которое мы превышаем, когда используем этот метод.

Однако исправить ситуацию очень легко. Мы можем использовать встроенный модуль под названием decimal, чтобы создать десятичный объект с гораздо более высокой точностью и подходящим для работы с уравнением размером:

import decimaldef formulaFibWithDecimal(n):    decimal.getcontext().prec = 10000    root_5 = decimal.Decimal(5).sqrt()    phi = ((1 + root_5) / 2)    a = ((phi ** n) - ((-phi) ** -n)) / root_5    return round(a)

В этой новой функции мы устанавливаем значение точности длиной 10000 цифр, преобразуем наше значение квадратного корня из 5 в десятичное значение объекта и используем его в нашем уравнении. Это позволяет нам легко вычислить 10000-е число в последовательности за поразительные 0,0692986 секунды, а это по сравнению со всеми нашими предыдущими методами огромное улучшение.

Расчёт 1000000-го числа Фибоначчи

Теперь вы, возможно, заметили, что формула работает медленнее итерационного решения, когда n=10000. Это связано с тем, что в формуле нам нужно создать десятичный объект и использовать его в уравнении, этот процесс занимает больше времени, чем повторение одной простой инструкции 10000 раз. Но история ещё не окончена.

Увеличение количества циклов может радикально увеличить длительность всего процесса. В какой-то момент, когда n составляет приблизительно 89200, время, необходимое итеративному решению для вычисления ответа, равно времени, которое необходимо при вычислении по формуле; когда же n увеличивается, время выполнения итеративного алгоритма возрастает с большей скоростью, чем время на решение по формуле.

График, показывающий время работы формулы Бине и итерационного решения

На графике видно точку пересечения времени выполнения формулы и итерационных графиков. Исходя из этого мы можем сказать, что с увеличением n время вычисления числа Фибоначчи по формуле возрастает линейно. Но при итеративном решении время увеличивается с увеличением n. Это даёт нам понять, что для вычисления миллионного числа Фибоначчи нам нужно использовать формулу. Дополнительное изменение, которое я должен был сделать, чтобы правильно вычислить число, увеличить точность моего десятичного объекта строкой кода decimal.getcontext().prec = 300000.

Ваше время выполнения алгоритма может отличаться. На моём компьютере, чтобы вычислить 1000000-е число Фибоначчи, потребовалось:

8,832661 секунды при решении с итерацией;
1,151380 секунды с формулой Бине, это в 7,7 раза быстрее!

Если вам хочется узнать число, оно состоит из 208988 цифр и в текстовом файле занимает 209 КБ:

Заключение

Вот так я вычислил миллионное число Фибоначчи, конечно, я мог бы вычислить число больше, но на самом деле для этого нет никакой реальной причины, и это заняло бы много времени, даже с использованием формулы Бине. Из приведённого выше графика я могу оценить затраты времени: чтобы вычислить миллиардное число Фибоначчи, мне потребуется примерно 310,8467 секунды, я оставлю это читателям. А чтобы получить специальность Fullstack-разработчик на Python потребуется немногим более года. Но можно и быстрее на нашем курсе студенты не привязаны к программе и скорость их прогресса зависит от них самих.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы

ПРОФЕССИИ

КУРС

Подробнее..

Категории: Python , Математика , Блог компании skillfactory , Рекурсия , Занимательные задачки , Числа , Задачки , Skillfactory , Фибоначчи , Заметки о производительности , Последовательности

Запрограммировано ли старение? Разбираем доказательства

22.02.2021 20:07:34 |

Автор: admin

Гипотеза о том, что старение запрограммировано весьма популярна среди обывателей, но имеет довольно мало сторонников среди ученых-геронтологов. При этом данная гипотеза кажется весьма логичной, на первый взгляд. Откуда такое расхождение? Может быть, ученые просто находятся в плену своих предубеждений и когнитивных ошибок, не давая зеленый свет смелой гипотезе?

"Ничто в биологии не имеет смысла, кроме как в свете эволюции"

Добржанский Феодосий Григорьевич

Для того, чтобы всерьез воспринимать гипотезу о наличии у абсолютного большинства видов некоей генетической программы старения нужны веские основания. Каким образом эволюция привела к тому, что гипотетическая генетическая программа закрепилась (далее просто Программа), какие преимущества она дает? Какую пользу старение может приносить отдельной особи никто так и не придумал, поэтому вся аргументация сторонников Программы сводится к групповому отбору. Групповой отбор - штука спорная, но давайте сделаем вид, что он существует и обратимся к работе Джоша Миттельдорфа, который является одним из сторонников Программы с довольно серьезным научным бэкграундом. Эта работа хороша тем, что она не заявляет голословно, что программа старения полезна для группы организмов, Миттельдорф приводит результаты симуляции, используя хорошо известную и проверенную модель популяционной динамики Лотки-Вольтерры. Давайте посмотрим на динамику численности популяций хищников и их добычи ("не-хищников") в разных сценариях (без старения и когда стареют жертвы):

Моделирование численности популяций нестареющих хищников и жертв.

Когда старения нет минимальная и максимальная численность обоих видов разнится на два порядка и довольно долгое время численность популяции находится возле нуля: малейшая флуктуация - и оба вида исчезнут! А теперь взглянем на результаты симуляции, где присутствует старение "не-хищников" и старые особи представляют более легкую добычу:

Моделирование численности популяций хищников и стареющих жертв.

Мы видим, что в этой симуляции динамика существенно стабилизировалась и есть даже некий намек на сходимость - колебания уменьшаются со временем. Это ли не лучшее доказательство наличия Программы!? Прежде чем ответить на этот вопрос, давайте изучим матчасть. А именно модель Лотки-Вольтерры, которую (с небольшими модификациями) использовал Джош Миттельдорф.

Модель Лотки-Вольтерры

"В сущности, все модели неправильны, но некоторые полезны"

Джордж Бокс

В 1925 году Лотка (и независимо от него в 1926 году Вольтерра) предложил модель взаимодействия двух видов типа хищник жертва, которая с успехом применяется и сейчас во многих задачах. Модель представляют собой простую систему дифференциальных уравнений и во многом похожа на ставшую печально известной в последнее время эпидемиологическую модель SIR (про которую можно почитать, например, тут).

$\frac{dx}{dt} = \alpha x - \beta xy$ $\frac{dy}{dt} = \delta xy - \gamma y$

x численность жертв (травоядных);
y численность хищников;
скорость роста популяции жертв;
вероятность того, что жертва будет съедена хищником при контакте;
1/ имеет смысл среднего времени до голодной смерти хищника;
вероятность того, что хищнику хватит еды на дальнейшее размножение.

Оставим пока хищников в покое и рассмотрим уравнение для жертв. Как будет выглядеть динамика их численности при условии, что все хищники куда-то внезапно исчезли (y=0)?

А вот как:

$\frac{dx}{dt} = \alpha x => x(t) = Сe^{\alpha t}$

То есть численность "не-хищников" по этой модели растет по экспоненте! И действительно, модель Лотки-Вольтерры предполагает что в распоряжении жертв неограниченные ресурсы (например, пища). Однако в реальности все совсем не так.

Логистическая модель роста

Вот как, например, выглядит рост численности популяции инфузорий туфелек (Paramecium):

Совершенно непохоже на экспоненциальный рост, не так ли? Современная наука давно объяснила почему так происходит и разработала простую математическую модель, которая точно описывает кривые роста бактерий, дрожжей, инфузорий и даже млекопитающих. И эта модель - рост по логистической кривой (эта кривая изображена черным на рисунке слева). Логистическая модель основана на факте наличия у среды определенной емкости - того максимального количества особей данного вида, которое среда может вместить и прокормить. Наличие такого предела приводит к тому, что скорость роста популяции замедляется по мере приближения к пределу, а при его достижении рост вообще прекращается.

Чем же обусловлено такое замедление? Существуют, как минимум, две группы факторов: механистические и адаптивные (генетические).

К механистическим можно, например, отнести недостаток пространства для размножения. Возьмем, к примеру, паразитическую осу, обитающую в Центральной Америке, которая откладывает яйца (см. рисунок снизу) только на спинках гусениц определенного вида. Очевидно, что максимальный прирост популяции равен количеству гусениц помноженному на количество яиц, которое можно разместить на гусенице. Таким образом ограничивается бесконечный экспоненциальный рост в данном случае. Такая же логика применима и к другим животным: например, существует предел того, сколько гнезд чайки могут разместить в ареале своего обитания, или предел подходящих мест для нереста лососей. Другим чисто механистическим препятствием является голод: если не хватает пищи, то даже если места полно, потомство либо вовсе не родится, либо умрет, не успев продолжить род.

Ко второй группе факторов можно отнести генетические адаптации: у мышей, например, в гипоталамусе обнаружили специальные нейроны, которые "отключают" репродуктивную функцию. Скорее всего, такие нейроны есть и у людей, потому что при экстремальной потере жировой массы женщины временно теряют фертильность. Снижение фертильности при голодании наблюдается и у более простых организмов [еще].

Подробнее про логистическую функцию

Логистическая функция является решением следующего дифференциального уравнения:

$\frac{dx}{dt} = \frac{(T - x) x}{T}$

Давайте поймем в чем физический смысл этого уравнения. Пусть x(t) - это функция роста численности некоей популяции от времени, тогда dx/dt - это скорость роста популяции. Понятно, что скорость роста зависит от того, сколько уже особей существует (просто потому что количество детей зависит от количества родителей). Но еще она зависит от множителя (T - x), где T - это некий предел численности популяции, который может обеспечить среда. Когда x = T, то dx/dt = 0, то скорость роста популяции нулевая независимо от того сколько уже особей есть на данный момент). Когда T намного больше x, то функция похожа на экспоненту, но по мере приближения x к T функция становится все более пологой. Это, кстати, похоже на динамику эпидемий и, действительно, рост числа новых случаев COVID-19 неплохо описывается таким простым дифференциальным уравнением. А все почему? Да потому что даже без ограничительных мер вследствие иммунитета (или смерти) у вируса остается все меньше свободных переносчиков для распространения и поэтому скорость распространения падает.

Давайте попробуем решить это уравнение:

$T \int \frac{dx}{(T - x)x} = \int dt$ $T \int \frac{dx}{(T - x)x} = \int (\frac{1}{T - x} + \frac{1}{x}) = -ln|T - x| + ln|x| + C_1$ $ln| \frac{x}{T - x}| = t + C_2 => \frac{x}{T - x} = e^{t+C_2} => x = Ce^t(T - x)$

Если мы будем рассматривать только значения x(t) >= 0, то можно избавиться от модуля и после несложных алгебраических манипуляций получим:

$x = Ce^t(T - x) => x(1 + Ce^t) = CTe^t => x(t) = \frac{CTe^t}{1 + Ce^t} = \frac{CT}{e^{-t}+C}$

Полученная нами функция является той самой логистической функцией, которая применяется для моделирования численности популяций, эпидемий, а также в машинном обучении: в логистической регрессии и искусственных нейросетях (хотя в последних ее уже практически не используют из-за проблемы затухания градиентов, но это совсем другая история). Вот такая вот интересная и полезная функция, которая берет начало из довольно простых соображений.

Итак, чтобы учитывать логистический рост популяции "не-хищников", я переписал первое уравнение Лотки-Вольтерры в следующем виде:

$\frac{dx}{dt} = \alpha (1 - \frac{x}{T})x - \beta xy$

И вот какую динамику популяций мне удалось получить:

Из графика видно, что замедления репродукции достаточно для стабилизации динамики численности популяций обоих видов! Более того, тут приведена модель другая модифицированная модель, которая учитывает миграцию животных, в рамках которой тоже легко достигается эквилибриум. В общем, нет никакой нужды в программе старения для сглаживания колебаний численности популяций - при использовании более приближенных к реальности моделей колебания исчезают сами по себе.

Есть и другая точка зрения на то, почему эволюция могла привести к закреплению программы старения:

Но в итоге эти виды, когда это преимущество уже закреплялось в генах достаточно большого количества особей, вымирали из-за голода, вызванного перенаселением, от которого такой вид страдал хотя бы один раз в течение миллионов лет эволюции. А избежали вымирания только те виды, в которых групповой отбор закрепил достаточное количество дублирующих механизмов старения, и те, которые научились пережидать голодные времена в виде спор или затаившихся яиц как нестареющая гидра. http://personeltest.ru/aways/habr.com/ru/post/405101/

Но спасает ли старение от перенаселения? Давайте рассмотрим простейший пример: пусть у нас есть бактерия, которая умирает от старения через 2 деления. Похожим образом стареют пекарские дрожжи Saccharomyces cerevisiae: от материнской клетки отпочковывается дочерняя клетка, которой достаются самые хорошие органеллы, а все плохие органеллы и клеточный мусор остаются в материнской клетке, которая через несколько десятков таких делений умирает. У дрожжей есть еще хронологическое старение, но это отдельная история.

Так как же будет выглядеть рост популяции в нашей простейшей модели очень быстрого старения? А вот как (см. рисунок внизу для пояснения):

1 бактерия
2 бактерии
4 бактерии - 1 умершая от старости = 3
6 бактерий - 1 умершая от старости = 5
10 бактерий - 2 умерших от старости = 8
16 бактерий - 3 умерших от старости = 13
...

Светлые кружочки - молодые бактерии, наполовину черные - старые, полностью черные - мертвые

1 2 3 5 8 13... Да это же последовательность чисел Фибоначчи (каждое число равно сумме двух предыдущих)! Но это в свою очередь означает, что старение никак не ограничивает экспоненциальный рост популяции, потому что последовательность Фибоначчи растет по экспоненте. Поэтому эволюция никак не могла прийти к программе старения с этой целью, но она вполне могла прийти к механизмам ограничения размножения, что ученые и обнаружили у мышей.

Это, конечно, не единственные попытки придать эволюционный смысл гипотезе запрограммированного старения, но Алекс Ковальд и Томас Кирквуд подробно разобрали математические модели "программистов" и в каждой из них нашли серьезные ошибки и/или несоответствия.

Также встречается такой аргумент, что существование эпигенетических часов, которые тесно коррелируют с возрастом человека (и других млекопитающих), является доказательством наличия программы старения. Но это является ничем иным как логической ошибкой: в автомобиле, например, есть одометр, показания которого (пробег авто) тесно коррелируют с возрастом автомобиля, однако это вовсе не означает, что автомобиль начинает функционировать хуже, потому что с определенного пробега включается специальная программа. Частные случаи, впрочем, могут быть, но в общем, это не так.

Подытожим:

Гипотетическая программа старения вредит индивидуальному отбору и НЕ дает никаких ощутимых преимуществ при групповом отборе (который до сих пор не является общепризнанным).
Гипотеза запрограммированного старения нарушает принцип бритвы Оккама: постулируется новая сущность без надобности (см. пункт 1).
До сих пор не найдено ни намека на генетическую программу старения у млекопитающих хотя другие генетические программы давно найдены (например, вышеупомянутая программа отключения фертильности)
Самое главное: не существует примеров взломов "программы старения" внутри одного вида. Если есть программа, значит, чисто статистически должны быть особи, у которых она ломается со временем. Например, у каждой клеточки нашего организма есть программа самоубийства (апоптоза), но она с завидной регулярностью ломается, что служит одним из механизмов патогенеза онкологических заболеваний. Где среди 7 миллиардов людей нестареющие мутанты с отключенной программой старения!? Ведь ожидаемая продолжительность жизни таких людей должна составлять как минимум сотни лет.

С эволюционной точки зрения старение по-прежнему лучше всего описывается различными модификациями гипотезы Медавара, которая сводится к тому, что в дикой природе смертность от старения у большинства видов пренебрежимо мала в сравнении со смертностью от внешних причин (болезни, хищники и т. п.) и поэтому мутации, которые увеличивают максимальную продолжительность жизни в популяции не закрепляются. Однако те виды, которые не испытывают такого давления среды (очень крупные животные или живущие в защищенной от хищников среде), живут гораздо дольше. Дальнейшим развитием идеи Медавара является гипотеза антагонистической плейотропии, которая утверждает, что в условиях дикой природы эволюция закрепит те варианты генов, которые могут снижать максимальную продолжительность жизни, но увеличивают вероятность репродуктивного успеха в молодости. Гипотеза Медавара была не единожды проверена экспериментально:

В лабораторных условиях эволюционные гипотезы можно эффективно проверять с помощью экспериментальных эволюционных парадигм. Это подразумевает применение специфичного режима отбора и проведение мониторинга эволюционных изменений на протяжении поколений. Например, Стернс и коллеги на протяжении 60 поколений применяли к одной группе плодовых мушек высокую случайную смертность, а к другой группе низкую случайную смертность. В результате оказалось, что режим высокой смертности приводил к укорочению продолжительности жизни, снижению возраста полового созревания и ускорению репродуктивной траектории по сравнению с режимом низкой смертности. Эти данные оказались полностью сопоставимыми с результатами природного эксперимента, в котором опоссумов, естественным образом эволюционирующих на лишенном хищников острове, сравнивали с опоссумами нормальной популяции на населенном хищниками материке.

Но это все эволюционные гипотезы, которые не описывают конкретные механизмы, а ознакомиться с наиболее правдоподобным на мой взгляд гипотетическим механизмом старения можно здесь.