Улучшение Фибоначчи рекурсия с BigIntegers


Мне была поставлена задача сделать быстро Фибоначчи рекурсивным методом, который использует BigInteger для расчета очень больших чисел. Однако, для вычисления числа последних 30 занимает почти менее 60 секунд каждый раз. К сожалению, я должен использовать некоторый тип рекурсии в мой метод, даже если итерации путь быстрее.

public static BigInteger theBigFib(int b) {
        BigInteger[] a = new BigInteger[100000];
        if(b < 2) {
            return BigInteger.ONE;
        }

        if(a[b] != null) {
            return a[b];
        }

        a[b] = theBigFib(b - 1).add(theBigFib(b - 2));
        return a[b];
    }

У меня есть цикл в моей основной, на котором работает метод от значения 20 до 30.

public static void main(String[] args) {
        final long start = System.nanoTime();
        for (int i = 20; i <= 30; i++) {
            System.out.println(theBigFib(i));
        }
    //  System.out.println(theBigFib(35));  Takes way too long
        final long end = System.nanoTime();
        System.out.println("This program took " + ((end - start) / 1000000000) + " second(s) to run.");
    }

Вот результаты из консоли. Это 2-й раз запустить его, которая первый раз вышла на 443 секунд.

10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
This program took 227 second(s) to run.

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



Комментарии
4 ответа

Эта линия вызывает много ненужных звонков:

a[b] = theBigFib(b - 1).add(theBigFib(b - 2));

На каждый второй звонок вы получаете 4 звонки, звонки, 8, 16 и т. д.

Вы все еще можете использовать рекурсию, но если добавить второй аргумент в метод, вы можете пройти как текущих, так и "промежуточный" результат (ФН-1 и ФН-2) и предотвращения двойного вызова. Пример использования int (вы можете переписать его BigInteger)

public class Fib {

public static void main(String[] args) {
System.out.println(fib(10));

}

private static int fib(int n) {

return fibInternal(0,1,n);

}

//Recursion here :)
private static int fibInternal(int a, int b, int n) {

if (n<=1)
return b;
else
return fibInternal(b, (a+b), n-1);
}
}

1
ответ дан 30 января 2018 в 10:01 Источник Поделиться

Каждый раз, когда вы называете theBigFibвы выделить новые BigInteger[] a объект. В результате, вы не кэширование всех предыдущих результатов.

1
ответ дан 30 января 2018 в 05:01 Источник Поделиться

Опираясь на предыдущий ответ, чтобы кэшировать результаты, вы должны иметь кэш быть статической переменной класса. Эта мелочь делает ваш код работать от 20 до 10000 в 1 секунду.

import java.math.BigInteger;

public class test{
private static BigInteger[] fibCache = new BigInteger[100000];
public static BigInteger theBigFib(int b) {
if(b < 2) {
return BigInteger.ONE;
}

if(fibCache[b] != null) {
return fibCache[b];
}

fibCache[b] = theBigFib(b - 1).add(theBigFib(b - 2));
return fibCache[b];
}
public static void main(String[] args) {
final long start = System.nanoTime();
for (int i = 20; i <= 10000; i++) {
System.out.println(theBigFib(i));
}
// System.out.println(theBigFib(35)); Takes way too long
final long end = System.nanoTime();
System.out.println("This program took " + ((end - start) / 1000000000) + " second(s) to run.");
}
}

1
ответ дан 30 января 2018 в 06:01 Источник Поделиться


public static BigInteger theBigFib(int b) {
BigInteger[] a = new BigInteger[100000];
if(b < 2) {
return BigInteger.ONE;
}

Как другие уже отметили, Вы можете улучшить это путем перемещения a из локальной переменной в статической переменной класса.

Вы можете также избавиться от условного статического инициализатора.

    private static final BigInteger[] fibCache = new BigInteger[100000];

static {
fibCache[0] = BigInteger.ONE;
fibCache[1] = BigInteger.ONE;
}

public static BigInteger theBigFib(int b) {
if (fibCache[b] == null) {
fibCache[b] = theBigFib(b - 1).add(theBigFib(b - 2));
}

return fibCache[b];
}

Судя по тому, как вы его называете (всегда с увеличением числа), это будет иметь эффект сохранения условного проверить на каждый звонок после первого. Т. е. после того, как вы кэшированные 2 и 3, которые условно не раз, потому что вы никогда не рекурсия, что далеко вниз.

Это также делает его легче для переключения от версии последовательности Фибоначчи, который начинается 1, 1 к варианту, который начинается 0, 1.

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

Я хотел бы объявить fibCache как final, поскольку вы никогда не перезаписывайте его с другим массивом. Это может также предусматривать некоторые оптимизации компилятора, так как он может использовать указатель, а не ручкой, чтобы ссылаться на него. Вам нужно только оставить он Мутабельный, если вы хотите изменить позже массива.

Поскольку вы возвращаете то же самое в нуль и не нуль случаях, я бы предпочел, чтобы проверить на null и повторить. Иначе вам придется писать два раза возврат. Таким образом, вы только один раз написать. Конечно, это только одна строка кода, но это на одну строку в метод, который должен всего пять, даже с пробелами.

0
ответ дан 30 января 2018 в 01:01 Источник Поделиться