Java 8中记忆的无限Fibonacci序列

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

由于我专注于JS编码，我实现了自己的JS懒惰函数库来进行概念validation。

https://github.com/kenokabe/spacetime

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

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无限序列定义为数学定义，然后使用延迟求值计算无限序列的必需部分。

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

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

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

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

Java8

 IntStream natural = IntStream.iterate(0, i -> i + 1); natural .limit(10) .forEach(System.out::println); 

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

但是，我想知道是否可以像以前那样定义它，也就是说，

JavaScript的

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

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

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

我寻求网络generate不确定的Fibonacci序列，我发现最好的结果

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

Java8

 private static Map 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)); } 

这不是一个无限的序列（Java8中的惰性Stream ）。

和

为流生成提供限制条件

Java8

 Stream.generate(new Supplier() { 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中的惰性Stream ），你可以说它被定义为Math。 但是我不喜欢这个实现，因为正如你所看到的，有许多内部有价值的获取序列，如n1 n2 n3然后是fibonacci ，因此代码结构复杂， 你需要控制可逆状态，这是反function的方式 – 与数学定义不同，可能这不是记忆。

所以，这是我的问题。 使用Java8 Stream ，是否有任何方法可以编写代码来以简洁的数学方式定义斐波那契的无限序列，并使用memoization

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 }); 

谢谢你的想法。

Answer 1

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

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

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

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

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

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