Chuỗi Fibonacci vô hạn với bản ghi nhớ trong Java 8

Question

Thứ nhất, tôi là một lập trình viên JavaScript, và khá mới đối với Java8 và thử tính năng chức năng mới.

Vì tôi chuyên môn hóa mã JS, tôi đã triển khai thư viện JS chức năng lười biếng của riêng mình để chứng minh khái niệm.

https://github.com/kenokabe/spacetime

Sử dụng thư viện, tôi có thể viết chuỗi Infinite các số nguyên và Fibonacci như sau:

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

rõ ràng đủ. Vấn đề là tôi có thể định nghĩa chuỗi vô hạn tự nhiên/Fibonacci như định nghĩa toán học như nó, sau đó tính toán phần bắt buộc của chuỗi vô hạn với đánh giá lười biếng.

Vì vậy, bây giờ tôi tự hỏi liệu tôi có thể làm theo cách tương tự với Java8 hay không.

Đối với chuỗi tự nhiên, tôi đã đăng câu hỏi khác tại đây.

Infinite sequence of Natural numbers with Java8 generator

Một trong những cách để xác định thứ tự tự nhiên là sử dụng iterator của Java8:

Java8

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

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

tôi quan sát IntStream natural = IntStream.iterate(0, i -> i + 1); là một định nghĩa hợp lý của các số tự nhiên trong toán học giác quan.

Tuy nhiên, tôi tự hỏi, nếu nó có thể xác định nó như tôi đã làm trước đây, có nghĩa là,

Javascript

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

vì điều này có vẻ ngắn gọn hơn. Thật không may, các câu trả lời cho thấy nó có thể không thể ngay cả khi chúng tôi sử dụng generate.

Ngoài ra, IntStream.iterate không phù hợp với chuỗi Fibonacci.

tôi tìm kiếm web để generate chuỗi vô hạn của Fibonacci, kết quả tốt nhất mà tôi tìm thấy là

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

Đây không phải là một chuỗi vô hạn (lười biếng Stream trong Java8).

và

Providing Limit condition on Stream generation

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

Đây là một dãy vô hạn (lười biếng Stream trong Java8), và bạn có thể nói nó được định nghĩa như Math. Tuy nhiên, tôi không thích việc triển khai này, vì bạn có thể thấy, có nhiều giá trị nội bộ để có được chuỗi như n1n2n3 rồi fibonacci, cho phù hợp với cấu trúc mã phức tạp và bạn cần kiểm soát trạng thái có thể thay đổi chức năng cách - không giống như định nghĩa toán học, và có lẽ điều này không được ghi nhớ.

Vì vậy, đây là câu hỏi của tôi. Với Java8 Stream, có cách nào để viết một mã số để xác định dãy vô hạn các fibonacci theo cách toán học súc tích với memoization như

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

Cám ơn suy nghĩ của bạn.

Answer 1

Bạn có thể lấy bản đồ dựa trên fibonacci memoized của bạn (x) và làm cho một dòng vô hạn ra khỏi nó như thế này:

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

Nhưng cách dễ nhất để làm cho một dòng vô hạn các số fibonacci là như thế này:

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

Khi bài viết bạn liên kết chỉ ra, "vô hạn" thực sự có nghĩa là "cho đến khi tràn dài" diễn ra nhanh chóng. Nếu bạn muốn tạo hàng trăm số mã, thay thế dài bằng 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]);