是否有可能在Java 8中创建一个无限增长的懒惰方式集合，由递归定义？ [英] Is it possible to create in Java 8 a unlimitedly growing in lazy way collection, defined by recursion?
问题描述
我可以创建一个递归闭包：
I can create a recursive closure:
static IntUnaryOperator fibo;
fibo =
(i) ->
i<2 ? 1 : fibo.applyAsInt(i-1)+ fibo.applyAsInt(i-2);
但当然，它仅作为一个例子。为了有用，这样的集合应该保留一次计数元素并得到（）它们而不重述。元素的计数应该在最初需要时以懒惰的方式进行。因此，不必多次计算任何成员。通过这种方式，我们将看到一个看起来像递归定义的序列的结构，并且将是快速且可重用的。
But of course, it has sense only as an example. To be useful, such collection should keep already once counted elements and get() them without recounting. The counting of elements should happen in lazy way, at first need. Thus, no member will have to be calculated more than once. In such way we'll a structure that will look like a recursively defined sequence, and will be fast and reusable.
当我开始学习Java 8时，我认为Stream以这种方式工作。但它没有，因为流不能使用两次。
When I started to study Java 8 I thought that Stream works in that way. But it does not, for the stream cannot be used twice.
我考虑过以下结构：
IntStream fi;
fi=IntStream.iterate(0, i -> fi[i-1]+fi[i-2]);
但是那样它不起作用 - 我无法通过索引从流中获取项目另一个问题是，如果我以后再沿着这条小溪走，那么它就会消耗掉，我不能反复使用它。如果我将流复制到List，它就不再是懒惰了。
But that way it won't work - I can't get an item from the stream by index.The other problem is that if I'll later go along the stream, it will be consumed and I can't use it repeatedly. If I copy the stream to List, it is not lazy anymore.
因此，我需要一些可以通过索引解决的构造。如 fibo（i）。
As a result, I need some construction that I can address by index. As fibo(i).
编辑。显然，解决方案不能是流，因为流不能使用两次。我不想在每次调用F（i）时重复所有计算。
Edit. Obviously, the solution cannot be a stream, for the stream cannot be used twice. I don't want to repeat all calculations on every call to F(i).
推荐答案
解决方案将创建为class FunctionalSequence 用于表示由具有整数参数的lambda函数定义的惰性无限对象序列。该函数可以是迭代的，也可以不是。对于迭代情况， FunctionalSequence 类将具有用于设置起始值的方法 initialize 。
The solution will be created as a class FunctionalSequence for representation of a lazy, infinite sequence of objects, defined by a lambda function with integer argument. The function can be iterative or not. For the iterative case the FunctionalSequence class will have a method initialize for setting the start values.
此类对象的声明如下：
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示例中一样，我们不能声明对象并以递归方式定义它在一个运营商。一个运算符用于声明，另一个用于定义。
Notice, as in the recursive lambda example in the question, we cannot declare the object and define it recursively in one operator. One operator for declaration, another for definition.
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中，我们应该组织递归，以便在这种情况下整个递归序列将回滚而不会真正遇到任何更改并抛出异常。
As the recursive function could easily meet the StackOverflowError, we should organize the recursion so that in that case the whole recursive sequence will roll back without any changes really met and throw the exception.
使用FunctionalSequence看起来如此：
The use of the FunctionalSequence could look so:
// 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");
}
}
最后一项功能可以通过以下方式使用：
The last function can be used in the following way:
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）：
Here are the results (the stack was limited to 256K for the needs of testing):
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）变得可达。我们成功了！
Look, the repeatable call of the f(i) for the same index takes practically no time - no iterations were made. We cannot reach f(1100) at once because of the StackOverflowError. But after we have reached once f(200), f(1100) becomes reachable. We made it!
这篇关于是否有可能在Java 8中创建一个无限增长的懒惰方式集合，由递归定义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
