是否可以在Java 8中创建一个由递归定义的无限增长的懒惰方式集合

Question

我可以创建一个递归闭包：

static IntUnaryOperator fibo;
fibo = 
    (i) -> 
    i<2 ? 1 : fibo.applyAsInt(i-1)+ fibo.applyAsInt(i-2);

但是，当然，它仅作为一个例子有意义。为了有用，这样的集合应该保留已经计数过的元素，并在不重新计数的情况下获取((它们。元素的计数应该在最初需要时以懒惰的方式进行。因此，任何成员都不必多次计算。通过这种方式，我们将创建一个看起来像递归定义的序列的结构，并且将是快速和可重用的。

当我开始学习Java 8时，我认为Stream就是这样工作的。但它没有，因为流不能使用两次。

我想到了以下结构：

IntStream fi;
fi=IntStream.iterate(0, i -> fi[i-1]+fi[i-2]);

但这样它就行不通了 - 我无法按索引从流中获取项目。另一个问题是，如果我以后沿着溪流走，它会被消耗掉，我不能重复使用它。如果我将流复制到列表，它不再懒惰了。

因此，我需要一些可以通过索引解决的构造。如fibo(i).

显然，解决方案不能是流，因为流不能使用两次。我不想在每次调用 F(i( 时重复所有计算。

Answer 1

看来你要求这样的东西：

public class Fibonacci extends AbstractList<BigInteger> {
    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE },
           p->new BigInteger[]{ p[1], p[0].add(p[1]) }).map(p -> p[0]);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
    @Override
    public BigInteger get(int index) {
        return stream().skip(index).findFirst().get();
    }
}

它可以通过List接口访问(由于充分的理由，它没有实现RandomAccess(，因此，您可以通过get(n)请求第 n 个值。请注意，get 的实现提示了如何在 Integer.MAX_VALUE 之后的位置获取值。只需使用stream().skip(position).findFirst().get().

小心！正如您所要求的那样，此列表是无限的。不要要求它对所有元素进行操作，例如甚至不是toString()。但像下面这样的事情会顺利进行：

System.out.println(new Fibonacci().subList(100, 120));

或

for(BigInteger value: new Fibonacci()) {
    System.out.println(value);
    if(someCondition()) break;
}   

但是，当您必须处理大型元素序列并希望有效地完成时，应确保在迭代器或流上工作O(n²)以避免重复get调用的复杂性。

请注意，我将元素类型更改为BigInteger因为在斐波那契数列和int或long值类型方面考虑无限流是没有意义的。即使使用 long 值类型，序列在只有 92 个值后结束，因为此时会发生溢出。

---

更新：既然您明确表示正在寻找惰性存储，您可以更改上面的类，如下所示：

public class Fibonacci extends AbstractList<BigInteger> {
    final Map<BigInteger,BigInteger> values=new HashMap<>();
    public Fibonacci() {
        values.put(BigInteger.ONE, BigInteger.ONE);
        values.put(BigInteger.ZERO, BigInteger.ONE);
    }
    @Override
    public BigInteger get(int index) {
        return get(BigInteger.valueOf(index));
    }
    public BigInteger get(BigInteger index) {
        return values.computeIfAbsent(index, ix ->
            get(ix=ix.subtract(BigInteger.ONE)).add(get(ix.subtract(BigInteger.ONE))));
    }
    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(BigInteger.ZERO, i->i.add(BigInteger.ONE)).map(this::get);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
}

我在这里使用BigInteger作为键/索引来满足(理论上(无限的要求，尽管我们也可以在所有实际用途中使用long键。关键点是最初空的存储：(现在使用 long 的示例(：

final Map<Long,BigInteger> values=new HashMap<>();

它使用应结束每次递归的值进行预初始化(除非由于已经计算的值而提前结束(：

values.put(1L, BigInteger.ONE);
values.put(0L, BigInteger.ONE);

然后，我们可以通过以下方式请求一个延迟计算的值：

public BigInteger get(long index) {
    return values.computeIfAbsent(index, ix -> get(ix-1).add(get(ix-2)));
}

或委托给上述get方法的流：

LongStream.range(0, Long.MAX_VALUE).mapToObj(this::get);

这创建了一个"实际上无限"的流，而上面的完整示例类，使用 BigInteger 理论上是无限的......

Map将记住序列的每个计算值。

Answer 2

我想不出一个好的通用解决方案，但是如果您想专门访问前面的两个元素，则可以以非常简单的方式定义自定义Spliterator，如下所示：

public static IntStream iterate(int first, int second, IntBinaryOperator generator) {
    Spliterator.OfInt spliterator = new AbstractIntSpliterator(Long.MAX_VALUE, 
                                             Spliterator.ORDERED) {
        int prev1 = first, prev2 = second;
        int pos = 0;
        @Override
        public boolean tryAdvance(IntConsumer action) {
            if(pos < 2) {
                action.accept(++pos == 1 ? prev1 : prev2);
            } else {
                int next = generator.applyAsInt(prev1, prev2);
                prev1 = prev2;
                prev2 = next;
                action.accept(next);
            }
            return true;
        }
    };
    return StreamSupport.intStream(spliterator, false);
}

用法：

iterate(1, 1, Integer::sum).limit(20).forEach(System.out::println);

Answer 3

该解决方案将创建为类FunctionalSequence，用于表示由具有整数参数的 lambda 函数定义的惰性无限对象序列。该函数可以是迭代的，也可以不是迭代的。对于迭代情况，FunctionalSequence类将具有用于设置起始值的方法initialize。

此类对象的声明如下所示：

    FunctionalSequence<BigInteger> fiboSequence =  new FunctionalSequence<>();
    fiboSequence.
        initialize(Stream.of(BigInteger.ONE,BigInteger.ONE)).
        setSequenceFunction(
            (i) ->
            fiboSequence.get(i-2).add(fiboSequence.get(i-1))
        );

请注意，就像问题中的递归 lambda 示例一样，我们不能在一个运算符中声明对象并递归定义它。一个运算符用于声明，另一个运算符用于定义。

FunctionalSequence类定义：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.stream.Stream;
public class FunctionalSequence<T> implements Iterable<T>{
    LinkedList<CountedFlighweight<T>> realList = new LinkedList<>();
    StackOverflowingFunction<Integer, T> calculate = null;
    public FunctionalSequence<T> initialize(Stream<T> start){
        start.forEachOrdered((T value) ->
        {
                realList.add(new CountedFlighweight<>());
                realList.getLast().set(value);
        });
        return this;
    }
    public FunctionalSequence<T>  setSequenceFunction(StackOverflowingFunction<Integer, T> calculate){
        this.calculate = calculate;
        return this;
    }
    @Override
    public Iterator<T> iterator() {
        return new SequenceIterator();
    }
    public T get(int currentIndex) throws StackOverflowError{
        if(currentIndex < 0) return null;
        while (currentIndex >= realList.size()){
            realList.add(new CountedFlighweight<T>());
        }
        try {
            return (T) realList.get(currentIndex).get(calculate, currentIndex);
        } catch (Exception e) {
            return null;
        }
    }
    public class SequenceIterator implements Iterator<T>{
        int currentIndex;
        @Override
        public boolean hasNext() {
            return true;
        }
        @Override
        public T next() {
            T result = null;
            if (currentIndex == realList.size()){
                realList.add(new CountedFlighweight<T>());
            }
            // here the StackOverflowError catching is a pure formality, by next() we would never cause StackOverflow
            try {
                result = realList.get(currentIndex).get(calculate, currentIndex);
            } catch (StackOverflowError e) {
            }
            currentIndex++;
            return result;
        }
    }
    /**
     * if known is false, the value of reference is irrelevant
     * if known is true, and reference is not null, reference contains the data
     * if known is true, and reference is null, that means, that the appropriate data are corrupted in any way
     * calculation on corrupted data should result in corrupted data.
     * @author Pet
     *
     * @param <U>
     */
    public class CountedFlighweight<U>{
        private boolean known = false;
        private U reference;
        /**
         * used for initial values setting 
         */
        private void set(U value){
            reference = value;
            known = true;
        }
        /**
         * used for data retrieval or function counting and data saving if necessary
         * @param calculate
         * @param index
         * @return
         * @throws Exception
         */
        public U get(StackOverflowingFunction<Integer, U> calculate, int index) throws StackOverflowError{
            if (! known){
                if(calculate == null) {
                    reference = null;
                } else {
                    try {
                        reference = calculate.apply(index);
                    } catch (Exception e) {
                        reference = null;
                    }
                }
            }
            known = true;
            return reference;
        }
    }
    @FunctionalInterface
    public interface StackOverflowingFunction <K, U> {
        public U apply(K index) throws StackOverflowError;
    }
}

由于递归函数很容易满足 StackOverflowError，我们应该组织递归，以便在这种情况下，整个递归序列将回滚而没有真正满足任何更改并抛出异常。

FunctionalSequence 的使用可能如下所示：

    // by iterator:
    int index=0;
    Iterator<BigInteger> iterator = fiboSequence.iterator(); 
    while(index++<10){
        System.out.println(iterator.next());
    }

左右：

static private void tryFibo(FunctionalSequence<BigInteger> fiboSequence, int i){
    long startTime = System.nanoTime();
    long endTime;
    try {
        fiboSequence.get(i);
        endTime = System.nanoTime();
        System.out.println("repeated timing for f("+i+")=" + (endTime-startTime)/1000000.+" ns");
    } catch (StackOverflowError e) {
        endTime = System.nanoTime();
        //e.printStackTrace();
        System.out.println("failed counting f("+i+"), time=" + (endTime-startTime)/1000000.+" ns");
    }       
}

最后一个函数可以通过以下方式使用：

    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 200);
    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 2100);
    tryFibo(fiboSequence, 2100);
    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 200);
    tryFibo(fiboSequence, 1100);

以下是结果(出于测试需求，堆栈限制为 256K(：

1
1
2
3
5
8
13
21
34
55
failed counting f(1100), time=3.555689 ns
repeated timing for f(100)=0.213156 ns
repeated timing for f(100)=0.002444 ns
repeated timing for f(200)=0.266933 ns
repeated timing for f(1100)=5.457956 ns
repeated timing for f(2100)=3.016445 ns
repeated timing for f(2100)=0.001467 ns
repeated timing for f(1100)=0.005378 ns
repeated timing for f(100)=0.002934 ns
repeated timing for f(100)=0.002445 ns
repeated timing for f(200)=0.002445 ns
repeated timing for f(1100)=0.003911 ns

看，对同一索引的 f(i( 的可重复调用几乎不需要时间 - 没有进行迭代。由于 StackOverflowError 的原因，我们无法一次达到 f(1100(。但是在我们达到一次f(200(之后，f(1100(变得可以到达。我们成功了！