Воспоминание с вавром кажется несостоятельным

Когда функция определена следующим образом

static Function1<BigInteger, BigInteger> fibonacci = Function((BigInteger value) ->
            value.equals(BigInteger.ZERO) ? BigInteger.ZERO
                    : value.equals(BigInteger.ONE) ? BigInteger.ONE
                    : value.equals(BigInteger.valueOf(2)) ? BigInteger.ONE
                    : Program.fibonacci.apply(value.subtract(BigInteger.ONE)).add(Program.fibonacci.apply(value.subtract(BigInteger.valueOf(2))))
    ).memoized();

И позвонил

System.out.println(fibonacci.apply(BigInteger.valueOf(1000)));

Он рассчитывается очень быстро. Однако, если я перемещу memoized() в функциональную переменную следующим образом

static Function1<BigInteger, BigInteger> fibonacci = Function((BigInteger value) ->
            value.equals(BigInteger.ZERO) ? BigInteger.ZERO
                    : value.equals(BigInteger.ONE) ? BigInteger.ONE
                    : value.equals(BigInteger.valueOf(2)) ? BigInteger.ONE
                    : Program.fibonacci.apply(value.subtract(BigInteger.ONE)).add(Program.fibonacci.apply(value.subtract(BigInteger.valueOf(2))))
    ); // Removed memoized() from here

И позвонил

fibonacci.memoized().apply(BigInteger.valueOf(1000));

Это занимает очень много времени, как если бы memoized() не применялся.

В чем может быть причина?


java vavr
person ozgur    schedule 02.11.2017    source источник
comment
Потому что а) рекурсия не вызывается в мемоизированной форме, б) весь смысл мемоизации заключается в том, что вам нужно сохранять мемоизацию, а не создавать новую мемоизацию каждый раз.   -  person Louis Wasserman    schedule 02.11.2017
comment
Думаю, я понял. Мой второй пример запомнен только для 1000. Остальные значения вызываются из raw fibonacci (). Можете ли вы ответить на вопрос, чтобы я согласился?   -  person ozgur    schedule 02.11.2017
comment
Почему вы не используете формулу Бине для вычисления Фибоначчи? mathworld.wolfram.com/BinetsFibonacciNumberFormula.html   -  person Samir    schedule 03.11.2017
comment
@SamirAghayarov Я думаю, это больше связано с экспериментами с функциональным программированием с использованием Фибоначчи в качестве игрушечного примера, а не с реальной потребностью в значениях функции.   -  person Nándor Előd Fekete    schedule 03.11.2017
comment
@ NándorElődFekete Именно так.   -  person ozgur    schedule 03.11.2017

Ответы (1)


arrow_upward
2
arrow_downward

Потому что а) рекурсия не вызывается в мемоизированной форме, б) весь смысл мемоизации заключается в том, что вам нужно сохранять мемоизацию, а не создавать новую мемоизацию каждый раз.

Program.fibonacci определяется в терминах самого себя, поэтому рекурсия вызывает эту версию, а не мемоизированную версию.

person Louis Wasserman    schedule 02.11.2017