如何实现用于流式传输斐波那契数的 Spliterator？
How to implement a Spliterator for streaming Fibonacci numbers?
我正在玩 Java 8 Spliterator 并创建了一个将斐波那契数流式传输到给定的 n。所以对于斐波那契数列 0, 1, 1, 2, 3, 5, 8, ...
n fib(n)
-----------
-1 0
1 0
2 1
3 1
4 2
以下是我的实现，它在 运行 超出堆栈内存之前打印一堆 1。你能帮我找到错误吗？ （我认为它没有推进 currentIndex 但我不确定将其设置为什么值）。
编辑 1：如果您决定回答，请保持与问题的相关性。这个问题不是关于高效的斐波那契数生成；这是关于学习分离器。
FibonacciSpliterator:
@RequiredArgsConstructor
public class FibonacciSpliterator implements Spliterator<FibonacciPair> {
private int currentIndex = 3;
private FibonacciPair pair = new FibonacciPair(0, 1);
private final int n;
@Override
public boolean tryAdvance(Consumer<? super FibonacciPair> action) {
// System.out.println("tryAdvance called.");
// System.out.printf("tryAdvance: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
action.accept(pair);
return n - currentIndex >= 2;
}
@Override
public Spliterator<FibonacciPair> trySplit() {
// System.out.println("trySplit called.");
FibonacciSpliterator fibonacciSpliterator = null;
if (n - currentIndex >= 2) {
// System.out.printf("trySplit Begin: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
fibonacciSpliterator = new FibonacciSpliterator(n);
long currentFib = pair.getMinusTwo() + pair.getMinusOne();
long nextFib = pair.getMinusOne() + currentFib;
fibonacciSpliterator.pair = new FibonacciPair(currentFib, nextFib);
fibonacciSpliterator.currentIndex = currentIndex + 3;
// System.out.printf("trySplit End: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
}
return fibonacciSpliterator;
}
@Override
public long estimateSize() {
return n - currentIndex;
}
@Override
public int characteristics() {
return ORDERED | IMMUTABLE | NONNULL;
}
}
斐波那契对：
@RequiredArgsConstructor
@Value
public class FibonacciPair {
private final long minusOne;
private final long minusTwo;
@Override
public String toString() {
return String.format("%d %d ", minusOne, minusTwo);
}
}
用法：
Spliterator<FibonacciPair> spliterator = new FibonacciSpliterator(5);
StreamSupport.stream(spliterator, true)
.forEachOrdered(System.out::print);
除了您的代码不完整之外，您的 tryAdvance 方法中至少有两个错误是可识别的。首先，你实际上并没有取得任何进步。您没有修改拆分器的任何状态。其次，您无条件地调用了操作的 accept 方法，这与您 returning 条件值而不是 true.
的事实不符
tryAdvance的目的是：
- 顾名思义，尝试前进，即计算下一个值
- 如果有下一个值，用那个值调用
action.accept 和 return true
- 否则只是 return
false
另外请注意，您的trySplit()看起来不太有说服力，我什至不知道从哪里开始。你最好继承 AbstractSpliterator 而不是实现自定义 trySplit()。无论如何，您的操作不会从并行执行中受益。如果您将使用该源构建的流与非常昂贵的 per-element 操作链接起来，那么它只能从并行执行中获得优势。
通常您不需要实现拆分器。如果你真的需要一个 Spliterator 对象，你可以为此使用流：
Spliterator.OfLong spliterator = Stream
.iterate(new long[] { 0, 1 },
prev -> new long[] { prev[1], prev[0] + prev[1] })
.mapToLong(pair -> pair[1]).spliterator();
测试：
for(int i=0; i<20; i++)
spliterator.tryAdvance((LongConsumer)System.out::println);
请注意，在 long 变量中保存斐波那契数是有问题的：它在斐波那契数 92 之后溢出。因此，如果您想创建仅迭代前 92 个斐波那契数的拆分器，我建议使用为此预定义的数组：
Spliterator.OfLong spliterator = Spliterators.spliterator(new long[] {
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073L, 4807526976L,
7778742049L, 12586269025L, 20365011074L, 32951280099L, 53316291173L, 86267571272L, 139583862445L,
225851433717L, 365435296162L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L,
4052739537881L, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L,
44945570212853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L,
498454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 3416454622906707L,
5527939700884757L, 8944394323791464L, 14472334024676221L, 23416728348467685L, 37889062373143906L,
61305790721611591L, 99194853094755497L, 160500643816367088L, 259695496911122585L, 420196140727489673L,
679891637638612258L, 1100087778366101931L, 1779979416004714189L, 2880067194370816120L,
4660046610375530309L, 7540113804746346429L
}, Spliterator.ORDERED);
数组拆分器也能很好地拆分，因此您将拥有真正的并行处理。
好的，让我们来编写拆分器。使用 OfLong 仍然太无聊：让我们切换到 BigInteger 并且不要将用户限制为 92。这里棘手的事情是快速跳转到给定的斐波那契数。为此，我将使用 here 描述的矩阵乘法算法。这是我的代码：
static class FiboSpliterator implements Spliterator<BigInteger> {
private final static BigInteger[] STARTING_MATRIX = {
BigInteger.ONE, BigInteger.ONE,
BigInteger.ONE, BigInteger.ZERO};
private BigInteger[] state; // previous and current numbers
private int cur; // position
private final int fence; // max number to cover by this spliterator
public FiboSpliterator(int max) {
this(0, max);
}
// State is not initialized until traversal
private FiboSpliterator(int cur, int fence) {
assert fence >= 0;
this.cur = cur;
this.fence = fence;
}
// Multiplication of 2x2 matrix, by definition
static BigInteger[] multiply(BigInteger[] m1, BigInteger[] m2) {
return new BigInteger[] {
m1[0].multiply(m2[0]).add(m1[1].multiply(m2[2])),
m1[0].multiply(m2[1]).add(m1[1].multiply(m2[3])),
m1[2].multiply(m2[0]).add(m1[3].multiply(m2[2])),
m1[2].multiply(m2[1]).add(m1[3].multiply(m2[3]))};
}
// Log(n) algorithm to raise 2x2 matrix to n-th power
static BigInteger[] power(BigInteger[] m, int n) {
assert n > 0;
if(n == 1) {
return m;
}
if(n % 2 == 0) {
BigInteger[] root = power(m, n/2);
return multiply(root, root);
} else {
return multiply(power(m, n-1), m);
}
}
@Override
public boolean tryAdvance(Consumer<? super BigInteger> action) {
if(cur == fence)
return false; // traversal finished
if(state == null) {
// initialize state: done only once
if(cur == 0) {
state = new BigInteger[] {BigInteger.ZERO, BigInteger.ONE};
} else {
BigInteger[] res = power(STARTING_MATRIX, cur);
state = new BigInteger[] {res[1], res[0]};
}
}
action.accept(state[1]);
// update state
if(++cur < fence) {
BigInteger next = state[0].add(state[1]);
state[0] = state[1];
state[1] = next;
}
return true;
}
@Override
public Spliterator<BigInteger> trySplit() {
if(fence - cur < 2)
return null;
int mid = (fence+cur) >>> 1;
if(mid - cur < 100) {
// resulting interval is too small:
// instead of jumping we just store prefix into array
// and return ArraySpliterator
BigInteger[] array = new BigInteger[mid-cur];
for(int i=0; i<array.length; i++) {
tryAdvance(f -> {});
array[i] = state[0];
}
return Spliterators.spliterator(array, ORDERED | NONNULL | SORTED);
}
// Jump to another position
return new FiboSpliterator(cur, cur = mid);
}
@Override
public long estimateSize() {
return fence - cur;
}
@Override
public int characteristics() {
return ORDERED | IMMUTABLE | SIZED| SUBSIZED | NONNULL | SORTED;
}
@Override
public Comparator<? super BigInteger> getComparator() {
return null; // natural order
}
}
对于非常大的 fence 值（如 100000），此实现实际上并行更快。可能更明智的实现也是可能的，它会不均匀地分割重用矩阵乘法的中间结果。
我正在玩 Java 8 Spliterator 并创建了一个将斐波那契数流式传输到给定的 n。所以对于斐波那契数列 0, 1, 1, 2, 3, 5, 8, ...
n fib(n)
-----------
-1 0
1 0
2 1
3 1
4 2
以下是我的实现，它在 运行 超出堆栈内存之前打印一堆 1。你能帮我找到错误吗？ （我认为它没有推进 currentIndex 但我不确定将其设置为什么值）。
编辑 1：如果您决定回答，请保持与问题的相关性。这个问题不是关于高效的斐波那契数生成；这是关于学习分离器。
FibonacciSpliterator:
@RequiredArgsConstructor
public class FibonacciSpliterator implements Spliterator<FibonacciPair> {
private int currentIndex = 3;
private FibonacciPair pair = new FibonacciPair(0, 1);
private final int n;
@Override
public boolean tryAdvance(Consumer<? super FibonacciPair> action) {
// System.out.println("tryAdvance called.");
// System.out.printf("tryAdvance: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
action.accept(pair);
return n - currentIndex >= 2;
}
@Override
public Spliterator<FibonacciPair> trySplit() {
// System.out.println("trySplit called.");
FibonacciSpliterator fibonacciSpliterator = null;
if (n - currentIndex >= 2) {
// System.out.printf("trySplit Begin: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
fibonacciSpliterator = new FibonacciSpliterator(n);
long currentFib = pair.getMinusTwo() + pair.getMinusOne();
long nextFib = pair.getMinusOne() + currentFib;
fibonacciSpliterator.pair = new FibonacciPair(currentFib, nextFib);
fibonacciSpliterator.currentIndex = currentIndex + 3;
// System.out.printf("trySplit End: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
}
return fibonacciSpliterator;
}
@Override
public long estimateSize() {
return n - currentIndex;
}
@Override
public int characteristics() {
return ORDERED | IMMUTABLE | NONNULL;
}
}
斐波那契对：
@RequiredArgsConstructor
@Value
public class FibonacciPair {
private final long minusOne;
private final long minusTwo;
@Override
public String toString() {
return String.format("%d %d ", minusOne, minusTwo);
}
}
用法：
Spliterator<FibonacciPair> spliterator = new FibonacciSpliterator(5);
StreamSupport.stream(spliterator, true)
.forEachOrdered(System.out::print);
除了您的代码不完整之外，您的 tryAdvance 方法中至少有两个错误是可识别的。首先，你实际上并没有取得任何进步。您没有修改拆分器的任何状态。其次，您无条件地调用了操作的 accept 方法，这与您 returning 条件值而不是 true.
tryAdvance的目的是：
- 顾名思义，尝试前进，即计算下一个值
- 如果有下一个值，用那个值调用
action.accept和 returntrue - 否则只是 return
false
另外请注意，您的trySplit()看起来不太有说服力，我什至不知道从哪里开始。你最好继承 AbstractSpliterator 而不是实现自定义 trySplit()。无论如何，您的操作不会从并行执行中受益。如果您将使用该源构建的流与非常昂贵的 per-element 操作链接起来，那么它只能从并行执行中获得优势。
通常您不需要实现拆分器。如果你真的需要一个 Spliterator 对象，你可以为此使用流：
Spliterator.OfLong spliterator = Stream
.iterate(new long[] { 0, 1 },
prev -> new long[] { prev[1], prev[0] + prev[1] })
.mapToLong(pair -> pair[1]).spliterator();
测试：
for(int i=0; i<20; i++)
spliterator.tryAdvance((LongConsumer)System.out::println);
请注意，在 long 变量中保存斐波那契数是有问题的：它在斐波那契数 92 之后溢出。因此，如果您想创建仅迭代前 92 个斐波那契数的拆分器，我建议使用为此预定义的数组：
Spliterator.OfLong spliterator = Spliterators.spliterator(new long[] {
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073L, 4807526976L,
7778742049L, 12586269025L, 20365011074L, 32951280099L, 53316291173L, 86267571272L, 139583862445L,
225851433717L, 365435296162L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L,
4052739537881L, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L,
44945570212853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L,
498454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 3416454622906707L,
5527939700884757L, 8944394323791464L, 14472334024676221L, 23416728348467685L, 37889062373143906L,
61305790721611591L, 99194853094755497L, 160500643816367088L, 259695496911122585L, 420196140727489673L,
679891637638612258L, 1100087778366101931L, 1779979416004714189L, 2880067194370816120L,
4660046610375530309L, 7540113804746346429L
}, Spliterator.ORDERED);
数组拆分器也能很好地拆分，因此您将拥有真正的并行处理。
好的，让我们来编写拆分器。使用 OfLong 仍然太无聊：让我们切换到 BigInteger 并且不要将用户限制为 92。这里棘手的事情是快速跳转到给定的斐波那契数。为此，我将使用 here 描述的矩阵乘法算法。这是我的代码：
static class FiboSpliterator implements Spliterator<BigInteger> {
private final static BigInteger[] STARTING_MATRIX = {
BigInteger.ONE, BigInteger.ONE,
BigInteger.ONE, BigInteger.ZERO};
private BigInteger[] state; // previous and current numbers
private int cur; // position
private final int fence; // max number to cover by this spliterator
public FiboSpliterator(int max) {
this(0, max);
}
// State is not initialized until traversal
private FiboSpliterator(int cur, int fence) {
assert fence >= 0;
this.cur = cur;
this.fence = fence;
}
// Multiplication of 2x2 matrix, by definition
static BigInteger[] multiply(BigInteger[] m1, BigInteger[] m2) {
return new BigInteger[] {
m1[0].multiply(m2[0]).add(m1[1].multiply(m2[2])),
m1[0].multiply(m2[1]).add(m1[1].multiply(m2[3])),
m1[2].multiply(m2[0]).add(m1[3].multiply(m2[2])),
m1[2].multiply(m2[1]).add(m1[3].multiply(m2[3]))};
}
// Log(n) algorithm to raise 2x2 matrix to n-th power
static BigInteger[] power(BigInteger[] m, int n) {
assert n > 0;
if(n == 1) {
return m;
}
if(n % 2 == 0) {
BigInteger[] root = power(m, n/2);
return multiply(root, root);
} else {
return multiply(power(m, n-1), m);
}
}
@Override
public boolean tryAdvance(Consumer<? super BigInteger> action) {
if(cur == fence)
return false; // traversal finished
if(state == null) {
// initialize state: done only once
if(cur == 0) {
state = new BigInteger[] {BigInteger.ZERO, BigInteger.ONE};
} else {
BigInteger[] res = power(STARTING_MATRIX, cur);
state = new BigInteger[] {res[1], res[0]};
}
}
action.accept(state[1]);
// update state
if(++cur < fence) {
BigInteger next = state[0].add(state[1]);
state[0] = state[1];
state[1] = next;
}
return true;
}
@Override
public Spliterator<BigInteger> trySplit() {
if(fence - cur < 2)
return null;
int mid = (fence+cur) >>> 1;
if(mid - cur < 100) {
// resulting interval is too small:
// instead of jumping we just store prefix into array
// and return ArraySpliterator
BigInteger[] array = new BigInteger[mid-cur];
for(int i=0; i<array.length; i++) {
tryAdvance(f -> {});
array[i] = state[0];
}
return Spliterators.spliterator(array, ORDERED | NONNULL | SORTED);
}
// Jump to another position
return new FiboSpliterator(cur, cur = mid);
}
@Override
public long estimateSize() {
return fence - cur;
}
@Override
public int characteristics() {
return ORDERED | IMMUTABLE | SIZED| SUBSIZED | NONNULL | SORTED;
}
@Override
public Comparator<? super BigInteger> getComparator() {
return null; // natural order
}
}
对于非常大的 fence 值（如 100000），此实现实际上并行更快。可能更明智的实现也是可能的，它会不均匀地分割重用矩阵乘法的中间结果。