6

我正在使用 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：如果您决定回答，请保持与问题相关。这个问题与有效的斐波那契数生成无关；这是关于学习拆分器的。

斐波那契分割器：

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

3 回答 3

4

除了您的代码不完整之外，您的方法中至少还有两个tryAdvance可识别的错误。首先，你实际上并没有取得任何进展。您没有修改拆分器的任何状态。其次，您无条件地调用操作的accept方法，该方法与您返回条件值而不是true.

的目的tryAdvance是：

  • 顾名思义，尝试提前，即计算下一个值
  • 如果有下一个值，则action.accept使用该值调用并返回true
  • 否则就返回false

进一步注意，你trySplit()看起来不太有说服力，我什至不知道从哪里开始。你最好继承AbstractSpliterator而不是实现 custom trySplit()。无论如何，您的操作不会从并行执行中受益。使用该源构建的流只有在将其与安静且昂贵的每个元素操作链接起来时才能从并行执行中获得优势。

于 2016-01-14T11:15:20.647 回答
4

一般来说，您不需要实现拆分器。如果你真的需要一个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);

数组拆分器也可以很好地拆分，因此您将拥有真正的并行处理。

于 2016-01-14T11:40:47.697 回答
3

好的，让我们编写拆分器。使用OfLong仍然太无聊：让我们切换到BigInteger并且不要将用户限制为 92。这里的棘手之处在于快速跳转到给定的斐波那契数。为此，我将使用此处描述的矩阵乘法算法。这是我的代码：

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），此实现实际上并行更快。可能更明智的实现也是可能的，它会不均匀地重用矩阵乘法的中间结果。

于 2016-01-15T09:46:32.110 回答