Первоначально я хотел написать этот аккуратный материал о том, как решение проблемы «получить число из последовательности Фибоначчи» может многому научить ВАС, но за последний год я понял, что программирование — это такой личный опыт, что я уверен, что Вы несправедливы, проповедуя и обучая вас.
Вместо этого я хотел бы сосредоточиться на своем собственном опыте с этим.
Несколько недель назад я решал проблему последовательности Фибоначчи:
Получив индекс, верните правильное число из последовательности Фибоначчи.
Я попробовал разные подходы, посмотрел, как это сделали другие, и узнал несколько удивительных вещей.
Рекурсия крутая, но может вводить в заблуждение
Одно решение, которое я видел, было рекурсивным. Рекурсия для меня всегда была волшебной. Частично потому, что вы должны подходить к проблеме с определенным мышлением, чтобы иметь возможность использовать рекурсию. И я редко когда-либо нахожу проблемы, требующие такого мышления.
В любом случае, поэтому я нашел решение и, просто взглянув на него, подумал, что это лучшее из когда-либо существовавших.
Во-первых, позвольте мне показать вам функциональное (математически функциональное) представление Фибоначчи:
F(n) = F(n-1) + F(n-2)
По сути, каждое число Фибоначчи равно сумме двух его предшественников. Рекурсивное решение очень похоже на математическое представление:
function fibRec(i) {
if (i < 2) {
return i;
} else {
return ( fibRec(i-1) + fibRec(i-2));
}
}
Я подумал про себя: «Это прекрасно! Так просто, и это описывает себя! Это ДОЛЖНО быть идеальным решением! » но это не так. Посмотрите, что происходит, когда вы запускаете эту аккуратную рекурсивную функцию:
Как видите, функция становится рекурсивно хуже с точки зрения производительности. Мы экспоненциально вычисляем одно и то же уравнение. Я бы назвал это «почти бесконечной петлей». Потому что мы вычисляем и пересчитываем одну и ту же проблему снова и снова и снова. Чем больше наша iприбыль, тем экспоненциально хуже рекурсия.
Поэтому я напомнил себе старую поговорку:
просто потому, что это выглядит правильно, это не значит, что это так.
Я узнал, что не каждая проблема, которая выглядит как рекурсивно разрешимая, должна решаться с помощью рекурсии. Технически это яркий пример того, как рекурсия отражает природу проблемы, но не является хорошим решением.
Затем приходит решение программно (или наивно)
У каждой проблемы есть неоправданное «наивное» решение. Я говорю «наивный», потому что это кажется неэффективным. Например, решение Фибоначчи с использованием простого программирования заключается в следующем:
//programmatically
function fibProg(i) {
var a = 0;
var b = 0;
var c = 0;
for(var d = 0; d < i+1; d++) {
if(d === 1) {
c = 1;
} else {
c = a+b;
}
a = b;
b = c;
}
return c;
}
Как вы можете видеть, мы должны отсчитывать от 0 до индекса каждый раз. Это ужасно неэффективно. Разве нет способа просто «пропустить» правильное число вместо этого итеративного подхода? Нет, не только программированием. Тем не менее, решение достаточно производительно, чтобы вы могли оставить его на этом. Не нужно идти дальше.
Решение рекурсии может привести к максимальным ошибкам в стеке вызовов, переполнениям и тому, что у вас есть. Это решение не будет, и оно будет работать эффективно до некоторого произвольного большого числа.
Математическое решение
Будучи бывшим специалистом по математике, я вспомнил, что есть формула решения Фибоначчи, основанная на золотом сечении. Быстрый поиск в Википедии привел к милому простому уравнению:
Я решил включить его в функцию и создать fibMathфункцию для решения:
function fibMath(i) {
var sqrtFive = Math.sqrt(5);
var firstHalf = 0;
var secondHalf = 0;
firstHalf = 1 / sqrtFive * Math.pow( ( ( 1 + sqrtFive ) / 2), i);
secondHalf = 1 / sqrtFive * Math.pow( ( (1 - sqrtFive ) / 2 ), i);
return Math.round(firstHalf - secondHalf);
}
Это довольно аккуратная, но совершенно непонятная функция для программиста. Тем не менее, производительность поражает.
Мне нравится, как математика может решать такие проблемы, как масло, с помощью инновационных формул. Я был озадачен и понял, что в программировании на фундаментальном математическом уровне есть вещи, которые я, возможно, не до конца понимаю, но позволяю нам работать со скоростью, с которой мы работаем.
Примечание. Кто-то указал мне, что функция Math.round () в конечном итоге приведет к неверным решениям из-за ошибки с плавающей запятой и аналогичных проблем. Есть некоторые обходные пути, если вам нужно быть точным и будете использовать эту функцию в реальном мире.
Тесты
Я решил протестировать все решения с JSPerf , небольшим классным приложением, которое использует Benchmark.js для тестирования производительности.
Я организовал как можно более честный тест и применил все три решения к работе.
Прежде всего, это тест, который позволяет использовать fibRec(рекурсивное решение). Я обнаружил, что maximum callошибка появляется в диапазоне от 50 или выше (возможно, даже ниже). Итак, я начал с получения 20-го индекса.
Проверьте это . Вот результаты для моего компьютера:
Для дальнейшего тестирования программных и математических решений я выбрал более высокий индекс для вычисления в «жестком режиме».
Проверьте это и увидите разницу:
Обратите внимание, что этот хардкорный режим тестирует индекс 54320 вместо 20. Интересно то, что, хотя математическое решение гораздо БОЛЬШЕ производительности, программное решение работает просто отлично. Если я не имею непосредственного отношения к математическим решениям, нет необходимости переходить к ядерному анализу и преобразовывать функции в математические представления (хотя это был бы интересный проект).
Я считаю, что программирование игр основано на математических формулах из-за этих различий, однако, они действительно запускают эти уравнения несколько миллионов раз в секунду.
Итак, я узнал об оптимизации
Разница между программным решением и математическим решением напоминает мне разницу между выполнением кода на нативной ассемблере и чем-то вроде PHP. Математическое решение похоже на магию, как и сборка (иногда). Но в большинстве случаев это не практично с точки зрения отладки, понимания и изменения.
Весь процесс научил меня, что важно избегать потенциальных узких мест, таких как первое решение, но также важно не зацикливаться на производительности таких решений, как решение для программирования. Я думал, что это будет медленно, но я ошибался. При 2000 операциях в секунду с очень высоким индексом поиска не о чем беспокоиться. Это эффективное решение.
Могу ли я сделать лучше? Да уж. И я сделал, математическое решение дало мне производительность в несколько раз выше, чем программирование. И если бы я использовал Фибоначчи или другие математические концепции в реальном мире, я бы усвоил урок, чтобы использовать умный способ, а не «ручной» (ручной, как, например, компьютер вычисляет решение вручную, а не прямо). до ответа).
Недостатком математического решения является то, что оно не всегда доступно для большинства реальных задач (за исключением видеоигр и 3D). Нематематическое решение достаточно хорошо, хотя и не должно быть отклонено.
С другой стороны, менее производительное, но понятное / поддерживаемое решение намного лучше, чем очень производительное, но неразборчивое, — это ловушка, которую следует избегать.
Я не знаю, имеет ли это смысл, но это было интересное упражнение.