У меня было немного свободного времени, я изучал некоторые концепции программирования и наткнулся на знаменитую последовательность Фибоначчи.
Хотя я не знал точной формулы, я знал, что можно вычислить конкретный номер последовательности, используя золотое сечение. Пока я искал это, я не нашел никакого компьютерного сравнения между этой реализацией и «другими». Поэтому я решил потратить некоторое время на это сам. По крайней мере, я надеюсь, что эта статья поможет кому-нибудь разгадать этот извечный вопрос интервью.
В этой статье я собираюсь изучить различные реализации и сравнить время их выполнения с использованием NodeJS. Эти реализации:
- Рекурсивный
- Рекурсивный с мемоизацией
- Динамическое программирование
- Золотое сечение
Рекурсивная реализация
Здесь нет ракетостроения. Если вы знакомы с рекурсией, это довольно простой подход. Однако, как только входные данные станут больше, стек вызовов JS начнет страдать. Обратите внимание, например, что для выполнения fibonacci (5) алгоритм выполняет fibonacci (3) 3 раза. См. Иллюстрацию ниже.
Рекурсивный с мемоизацией
Чтобы смягчить предыдущую проблему, мы можем улучшить текущее решение, добавив простое состояние памяти, которое предотвращает вычисление одного и того же значения дважды. Простое управление кешем.
Этот подход улучшает время выполнения, но увеличивает использование памяти, поскольку мы храним все предыдущие значения в нашей памяти. Как только мы начнем увеличивать ввод, объем выделяемой памяти должен будет увеличиться до определенного порога, и мы начнем разработку проблем с памятью. Обратите внимание, что мы используем механизм рекурсии, поэтому это также повлияет на стек вызовов.
Динамическое программирование
Подход к динамическому программированию немного другой. Он работает по принципу «вверх-вниз». Динамическое программирование, потому что мы используем пул переменных и не происходит увеличения памяти с первой и до последней итерации.
Поскольку этот подход на 100% итеративен, рекурсии нет, поэтому стек вызовов не пострадает. Этот подход будет работать для каждого ввода (хотя мы можем быть ограничены максимальным целочисленным значением).
Золотое сечение
Расчет золотого сечения, как следует из названия, позволяет нам вычислять последовательности Фибоначчи для определенного индекса, просто используя расчет. Вот несколько сайтов, которые я использовал в качестве источника: Fibonacci.com и MathIsFun.com.
Этот расчет является линейным. Делаем такой же расчет. Хотя время выполнения может немного зависеть от каждого вычисления (помните, что javascript не оптимизирован для операций со сложными числами).
Полученные результаты
Репозиторий GitHub со всем этим кейсом можно найти здесь.
Я использовал NodeJS process.hrtime () для расчета времени выполнения каждого алгоритма. Также экспортировал результаты в файлы. csv, поэтому я легко могу создавать графики с помощью простой таблицы Google.
Также создайте небольшую тестовую функцию, чтобы гарантировать правильность всех реализаций.
Чтобы улучшить видимость, мне пришлось создать 3 разных набора данных, сравнивающих эти реализации:
- Входов до 40
- Входы до 15к
- Входы до 10M
Примечание. Все значения времени выполнения указаны в миллисекундах.
Входов до 40
Вы можете проверить результаты здесь
На этом графике мы видим, что время выполнения простого рекурсивного решения быстро увеличивается. Это было ожидаемо. Давайте посмотрим, что произойдет с более крупными вложениями.
Входы до 15к
Для этого набора данных я удаляю простую рекурсивную реализацию.
Вы можете проверить результаты здесь
Существует значительный всплеск подхода к памяти вокруг входа 1k и снова, когда вход достиг 7,5k. Еще один для динамического подхода около 10 тысяч, я пока не могу его объяснить.
Но случилось одно: у нас начались проблемы со стеком вызовов, как только вход достиг 12,5 КБ. Это был пороговый предел для моей установки. Думаю, я мог бы увеличить размер стека, чтобы выполнение продолжалось, но это не идеально.
Входы до 10M
Для этого набора данных я использовал только динамический подход и расчет золотого сечения. Вот тогда все становится интереснее. Данные о результатах можно найти здесь.
Динамический подход отлично работал на 10М. Я уверен, что динамический подход будет работать до тех пор, пока мы не достигнем максимального целочисленного значения.
Однако, сравнивая время выполнения как в динамическом (14334768 мс), так и в золотом сечении (614 мс), мы наблюдаем сокращение в 23 тыс. Раз!
Заключение
Как мы и ожидали:
- Простой рекурсивный подход работает только для очень ограниченного ввода;
- Рекурсивный подход с кешем работает намного лучше, однако проблемы со стеком вызовов будут.
- Время выполнения динамического подхода увеличивается линейно с увеличением ввода, но по-прежнему может обеспечить результаты для большого числа
- Подход золотого сечения обеспечивает решение, практически линейное в отношении времени выполнения.
Лично я никому не рекомендую выполнять операции с большими числами с помощью JS!
Если вам интересно, я создал репозиторий GitHub со всеми реализациями и вспомогательными функциями для создания файлов .csv, так что любой может поиграть. Проверить это.
Скорее всего, никто не будет просить вас разработать калькулятор чисел Фибоначчи. Тем не менее, я не буду лгать, мне было весело исследовать это.
Надеюсь, вы нашли это интересным в какой-то форме.
Большое спасибо.
