Давайте рассмотрим фундаментальную проблему здесь. Вы хотите, чтобы ваш код работал быстрее на одном и том же оборудовании, важный программный процесс под названием оптимизация.
Во время оптимизации вам нужно будет профилировать ваше приложение, чтобы определить, что является самым медленным компонентом и улучшить его. В вашем случае я могу с достаточной степенью уверенности предположить, что самым медленным компонентом вашей программы является вызов функции. Заговор-й член Фибоначчи от числа вызовов функции мы получаем:
, как вы можете видеть, рост экспоненциальный. Примечание. Существуют математические способы понять это, в частности, как описано на this page. Экспоненциальный рост временной сложности всегда является чем-то, что можно избежать, если ваши намерения состоят в том, чтобы сделать быструю исполняемую функцию (предоставлено, есть функции, которые должны быть экспоненциальными, но это не один из них). Глядя на cycle(50), получив 4 * 10^10 вызовов функций, вы сказали, что закончили почти минуту, что соответствует примерно 666,6 миллиона вызовов функций в секунду (или 1 звонок за 1,5 нс), вряд ли кажется справедливым, чтобы вызвать java slow основываясь на этом.Суть в том, что не имеет значения, насколько хороши или быстренькие методы оптимизации компилятора, он не сможет исправить вашу временную сложность, он может только сделать каждую операцию немного быстрее (прочитайте tail-call optimization, если вы хотите узнать больше) ,
Основная проблема, с которой вы сталкиваетесь, заключается в том, что вы много раз повторяете одни и те же числа Фибоначчи, подумайте, сколько раз вы пересчитываете cycle(2). Вот откуда происходит экспоненциальная сложность, много раз повторяя одни и те же числа Фибоначчи, что бесполезно.
Самый простой способ решить проблему - через итерацию, но вы выразили свою незаинтересованность в итераторе.
Следующий простой способ - использовать таблицу поиска (LUT), в которой хранятся предварительно вычисленные числа Фибоначчи в массиве для быстрого доступа. Проблема с этим подходом может быть легко показано ниже:
Диаграмма выше показывает эффекты LUT н до 10. в то время как мы снизили мощность экспоненты, мы все же имеем дело с экспоненты, которые не решают проблему полностью (предположим, что вам нужно сделать cycle(100), что тогда?).
Решение должно использовать запоминание как указано в комментарии пользователя 1.618. Это означает, что сохраните результат каждого термина Фибоначчи, когда вы его вычисляете, генерируя LUT по мере того, как вы идете, никогда не переучивая результат дважды.
На следующем графике показано влияние этого:
на cycle(50), вам нужно 97 вызовов методов, которые со скоростью 1,5 нс/вызов завершится в 145,5 нс, быстрее вы можете моргнуть (это, вероятно, не будет так быстро из-за дополнительного времени, смотрящего на LUT, а также не разогревая).
Реализация этого в Java, мы получаем:
private static long[] fib_numbers;
public static long cycle(int x){
if(fib_numbers == null || fib_numbers.length <= x){
fib_numbers = new long[x + 1];
}
return cycle_rec(x);
}
private static long cycle_rec(int x) {
if(x <= 1){
return x;
}else if(fib_numbers[x] != 0){
// previously computed result exists, return directly
return fib_numbers[x];
}else{
// compute and store cycle(x)
fib_numbers[x] = cycle_rec(x-1)+cycle_rec(x-2);
return fib_numbers[x];
}
}
массив fib_numbers держит LUT мы динамически генерировать на вызов метода. Мы публикуем открытый метод cycle(), чтобы настроить массив для использования перед внутренним вызовом cycle_rec() (наша рекурсивная функция).
Memoize что функция! –
Конечно, я большой тип теории. Последовательность Фибоначчи была чем-то, что я планировал реализовать в солнечной энергии, когда был моложе. Жаль, что кто-то еще подумал об этом, прежде чем я смогу что-нибудь с этим сделать. Ха! – Jahhein
Вам нужно использовать рекурсию? Было бы гораздо быстрее просто перебирать последовательность. –