Java 8中记忆的无限Fibonacci序列 [英] Infinite Fibonacci Sequence with Memoized in Java 8

问题描述

首先，我是一名JavaScript程序员，对Java8很新，并尝试新功能。

Firstly, I'm a JavaScript programmer, and fairly new to Java8 and trying the new functional feature.

由于我专注于JS编码，我实现了自己的JS用于概念验证的惰性函数库。

Since I expertise JS coding, I implemented my own JS lazy-functional library for proof of concept.

https： //github.com/kenokabe/spacetime

使用该库，我可以编写自然数的无限序列和Fibonacci 下方：

Using the library, I could write Infinite sequence of Natural numbers and Fibonacci as below:

JavaScript

var spacetime = require('./spacetime');
var _ = spacetime.lazy(); 

var natural = _(function(n)   //memoized automatically
{
  return n;    // Natural numbers is defined as the `n`th number becomes `n`
});

var natural10 = _(natural)
  .take(10)
  .compute(function(x)
  {
    console.log(x);
  });


//wrap a recursive function to memoize
// must be at the definition in the same scope
var fib = _(function(n)
{
  if (n <= 1)
    return 1; // as the Fib definition in Math
  else
    return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
});

var fib10 = _(fib)
  .take(10)
  .compute(function(x)
  {
    console.log(x);
  });

足够清楚。关键是我可以将Natural / Fibonacci无限序列定义为数学定义，然后使用延迟求值来计算无限序列的必需部分。

Clear enough. The point is that I can define Natural/Fibonacci infinite sequence as the math definition as it is, then later compute the required part of the infinite sequence with lazy-evaluation.

所以，现在我想知道我是否可以用Java8做同样的方式。

So, now I wonder if I can do the same manner with Java8.

对于自然序列，我在这里发布了另一个问题。

For natural sequence, I had post another Question here.

使用Java8生成器的无限自然数序列

定义Natural序列的一种方法是使用Java8的 iterator ：

One of the way to define Natural sequence is to use iterator of Java8:

Java8

IntStream natural = IntStream.iterate(0, i -> i + 1);

natural
 .limit(10)
 .forEach(System.out::println);

我观察 IntStream natural = IntStream.iterate（0，i - > i + 1）; 是数学意义上的自然数的公平定义。

I observe IntStream natural = IntStream.iterate(0, i -> i + 1); is a fair definition of natural numbers in math sense.

然而，我想知道是否可以将其定义为I以前做过，就是

However, I wonder if it's possible to define it as I did before, that is,

JavaScript

var natural = _(function(n)   //memoized automatically
    {
      return n;    // Natural numbers is defined as the `n`th number becomes `n`
    });

因为这看起来更简洁。不幸的是，答案表明即使我们使用生成也可能无法实现。

because this looks more concise. Unfortunately, the answers suggest it's probably not possible even we use generate.

此外， IntStream.iterate 不适合Fibonacci序列。

In addition, IntStream.iterate does not fit for Fibonacci sequence.

我寻求网络生成不确定的Fibonacci序列，我发现的最佳结果是

I seek web to generate indefinite sequence of Fibonacci, the best results I found are

http://blog.informatech.cr/2013/05/08/memoized-fibonacci-numbers-with-java-8/

Java8

private static Map<Integer,Long> memo = new HashMap<>();
static {
   memo.put(0,0L); //fibonacci(0)
   memo.put(1,1L); //fibonacci(1)
}

//And for the inductive step all we have to do is redefine our Fibonacci function as follows:

public static long fibonacci(int x) {
   return memo.computeIfAbsent(x, n -> fibonacci(n-1) + fibonacci(n-2));
}

这不是无限序列（懒惰 Stream in Java8）。

This is not an infinite sequence (lazy Stream in Java8).

和

提供流生成限制条件

Java8

Stream.generate(new Supplier<Long>() {
    private long n1 = 1;
    private long n2 = 2;

    @Override
    public Long get() {
        long fibonacci = n1;
        long n3 = n2 + n1;
        n1 = n2;
        n2 = n3;
        return fibonacci;
    }
}).limit(50).forEach(System.out::println);

这是一个无限序列（懒惰流在Java8）中，您可以说它被定义为Math。
但是我不喜欢这个实现，因为正如你所看到的，有许多内部有价值的东西可以获得序列，例如 n1 n2 n3 然后斐波纳契，因此代码结构很复杂，你需要控制可变状态，这是反功能方式 - 与数学定义不同，可能这不是记忆。

This is an infinite sequence (lazy Stream in Java8), and you could say it's defined as Math. However I do not like this implementation because, as you can see, there are many internal valuable to obtain the sequence such as n1 n2 n3 then fibonacci, accordingly the code structure is complicated and you need to control mutable state which is anti-functional manner - unlike the math definition, and probably this is not memoized.

所以，这是我的问题。使用Java8 Stream ，有没有办法编写代码以简明的数学方式定义斐波纳契的无限序列，并具有类似

So, here's my question. With Java8 Stream, is there any way to write a code to define the infinite sequence of fibonacci in concise math manner with memoization like

JavaScript

 var fib = _(function(n)
    {
      if (n <= 1)
        return 1; // as the Fib definition in Math
      else
        return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
    });

感谢您的想法。

推荐答案

您可以使用基于地图的memoized fibonacci（x）并从中创建无限流：

You can take your map-based memoized fibonacci(x) and make an infinite stream out of it like this:

LongStream fibs = IntStream.iterate(1, i->i+1).mapToLong(i -> fibonacci(i));

但是，制作无限的斐波纳契数字流的最简单方法是这样的：

But the easiest way to make an infinite stream of fibonacci numbers is like this:

LongStream fibs = Stream.iterate(
        new long[]{1, 1},
        f -> new long[]{f[1], f[0] + f[1]}
).mapToLong(f -> f[0]);

正如您所链接的文章指出的那样，无限实际上意味着直到长时间溢出很快。如果你想生成数百个斐波纳契数，请用BigInteger代替long：

As the article you linked to points out, "infinite" really means "until long overflows" which happens quickly. If you want to generate hundreds of fibonacci numbers, replace long with BigInteger:

    Stream<BigInteger> bigFibs = Stream.iterate(
            new BigInteger[]{BigInteger.ONE, BigInteger.ONE},
            f -> new BigInteger[]{f[1], f[0].add(f[1])}
    ).map(f -> f[0]);

这篇关于Java 8中记忆的无限Fibonacci序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！