是否有可能在Java 8中创建由递归定义的惰性(更好的无限)集合？

Question

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

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

但当然,它只是作为一个例子.相反,如果我创建了一个惰性/无限列表/流,则可以以非常好的方式使用递归:不必多次计算任何成员.

我想到了以下结构:

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

但是那样它就行不通了 - 我无法通过索引从流中获取一个项目.另一个问题是,如果我以后再沿着流,它将被消耗,我不能重复使用它.如果我将流复制到List,它就不再是懒惰了.

因此,我需要一些我可以通过索引解决的构造.作为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),因此,您可以通过请求第n个值get(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因为在涉及Fibonacci序列和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

该解决方案将创建为一个类，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，因此我们应该组织递归，以便在这种情况下，整个递归序列将回滚，而不会真正遇到任何更改并抛出异常。

FunctionSequence 的使用可能如下所示：

    // 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) 就变得可达。我们做到了！