Мне потребовалось написать простую реализацию алгоритма Фибоначчи, а затем сделать его быстрее.
Вот моя первоначальная реализация
public class Fibonacci {
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return getFibonacciOf(n-2) + getFibonacciOf(n-1);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
}
Как вы можете видеть, я использую System.currentTimeMillis(), чтобы получить простую меру времени, прошедшего при вычислении Фибоначчи.
Эта реализация быстро становится экспоненциально медленной, как вы можете видеть на следующем рисунке
Итак У меня есть простая идея оптимизации. Чтобы поместить предыдущие значения в HashMap и вместо этого переучитывать их каждый раз, просто вернуть их из HashMap, если они существуют. Если они не существуют, мы помещаем их в HashMap.
Вот новая версия кода
public class FasterFibonacci {
private static Map<Long, Long> previousValuesHolder;
static {
previousValuesHolder = new HashMap<Long, Long>();
previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
}
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (previousValuesHolder.containsKey(Long.valueOf(n))) {
return previousValuesHolder.get(n);
} {
long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
previousValuesHolder.put(Long.valueOf(n), Long.valueOf(newValue));
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
Это изменение делает вычисления чрезвычайно быстрыми. Я вычисляю все значения от 2 до 103 в мгновение ока и получаю переполнение long в F (104) (Дает мне F (104) = -7076989329685730859, что неверно). Я нахожу это настолько быстрым, что ** Интересно, есть ли какие-либо ошибки в моем коде (спасибо за проверку и дайте мне знать, пожалуйста) **. Посмотрите на вторую картинку:
Правильно ли реализован алгоритм моего алгоритма фибоначчи (я думаю, что он для меня, потому что он получает те же значения, что и в первой версии, но поскольку первая версия была слишком медленной, я не мог вычислить с ней большие значения, такие как F (75) )? Каким другим способом я могу использовать его быстрее? Или есть лучший способ сделать это быстрее? Также как я могу вычислить Fibonacci для больших значений (например, 150, 200) без переполнения ** long **? Хотя это кажется быстрым, я хотел бы подтолкнуть его к пределам. Я помню, как мистер Абраш сказал: " Лучший оптимизатор находится между вашими двумя ушами", поэтому я считаю, что он все равно может быть улучшен. Спасибо, что помогли
[Замечание об издании:] Хотя вопрос этот затрагивает один из основных моментов моего вопроса, вы можете видеть сверху, что у меня есть дополнительные вопросы.
