Как сгенерировать числа Hexanacci в Java?

Я пытаюсь создать серию hexanacci в java с помощью BigInteger.

Серии: 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529 , 3621088, 7182728, 14247536, 28261168, 56058368 ...

Вот мой код:

import java.math.BigInteger;

/**
 *
 * @author Tushar
 */
public class Hexanacci {

    static int result = 0;

    public static void main(String[] args) {
        int dest = 33;
        System.out.println(calc(BigInteger.valueOf(dest)));
    }

    public static BigInteger calc(BigInteger n) {
        if (n.compareTo(BigInteger.ZERO) == 0) {

            return BigInteger.ONE;

        } else if (n.compareTo(BigInteger.ONE) == 0) {

            return calc(BigInteger.ZERO);

        } else if (n.compareTo(BigInteger.valueOf(2)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)));


        } else if (n.compareTo(BigInteger.valueOf(3)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)))
                    .add(calc(BigInteger.valueOf(2)));


        } else if (n.compareTo(BigInteger.valueOf(4)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)))
                    .add(calc(BigInteger.valueOf(2)))
                    .add(calc(BigInteger.valueOf(3)));


        } else if (n.compareTo(BigInteger.valueOf(5)) == 0) {


            return calc(BigInteger.ZERO)
                    .add(calc(BigInteger.ONE))
                    .add(calc(BigInteger.valueOf(2)))
                    .add(calc(BigInteger.valueOf(3)))
                    .add(calc(BigInteger.valueOf(4)));


        } else {


            return calc(n.subtract(BigInteger.valueOf(1)))
                    .add(calc(n.subtract(BigInteger.valueOf(2))))
                    .add(calc(n.subtract(BigInteger.valueOf(3))))
                    .add(calc(n.subtract(BigInteger.valueOf(4))))
                    .add(calc(n.subtract(BigInteger.valueOf(5))))
                    .add(calc(n.subtract(BigInteger.valueOf(6))));


        }
    }
}

Эта программа работает нормально, когда размер dest маленький. Но если я увеличу значение dest, его повесят. Например, когда dist равно 33, вычисление результата занимает почти 3 минуты:

3414621024
BUILD SUCCESSFUL (total time: 3 minutes 4 seconds)

Кто-нибудь может сказать мне, правильный это подход или нет?

Calc вызывает себя в худшем случае 6 раз рекурсивно, то есть O (n ^ 6).

— 07.07.2018 01:36

Возможное решение этой проблемы: мемоизация.

— 07.07.2018 01:51

java performance biginteger

07.07.2018 01:33

Пользовательский скаляр GraphQL

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...

Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами

В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...

Поднятие тревоги для долго выполняющихся методов в Spring Boot

Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...

Принятие принципов SOLID в Spring Boot: Создание обслуживаемых и масштабируемых приложений

Коллекции (ArrayList , HashSet , HashMap)

Полный курс Java для разработчиков веб-сайтов и приложений

Получите сертификат Java Web и Application Developer, используя наш курс.

238

Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Как упоминалось в комментариях, мемоизация - это простой способ улучшить код и ускорить работу. Создайте Map<BigInteger, BigInteger> для хранения промежуточных результатов. Что-то вроде,

static Map<BigInteger, BigInteger> memo = new HashMap<>();
static {
    int[] initial = { 0, 1, 1, 2, 4, 8 };
    for (int i = 0; i < initial.length; i++) {
        memo.put(BigInteger.valueOf(i), BigInteger.valueOf(initial[i]));
    }
}

public static BigInteger calc(BigInteger n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger orig = n, v = BigInteger.ZERO;
    for (int i = 0; i < 6; i++) {
        n = n.subtract(BigInteger.ONE);
        v = v.add(calc(n));
    }
    memo.put(orig, v);
    return v;
}

Что почти мгновенно возвращает тридцать третий член.

действительно удивительным.

— 07.07.2018 02:20

07.07.2018 02:10

I am trying to generate the hexanacci series

Чтобы сгенерировать серию до count, вы можете просто вычислить скользящая сумма, без рекурсии.

// Pseudo code:

int count = 80;
mySeries = vector<BigInteger>;

preallocate mySeries to size 'count' (or 'add' items in the loop)
prefill mySeries with 0, 1, 1, 2, 4, 8, 16, 32

for (int i = 8; i < count; i++) {

                  // avoid multiplication by 2, unless BigInteger supports '<< 1'
    mySeries[i] = mySeries[i-1] + mySeries[i-1] - mySeries[i-7];
}

Результаты должны быть мгновенными.

07.07.2018 18:42