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コードが不完全であるという事実に加えて、認識可能なメソッドに少なくとも 2 つのエラーがあります。まず、実際には前進していません。スプリッテレータの状態を変更していません。第 2 に、アクションのメソッドを無条件に呼び出していますが、acceptこれは ではなく条件付きの値を返しているという事実と一致しませんtrue。

の目的tryAdvanceは次のとおりです。

  • 名前が示すように、前進を試みます。つまり、次の値を計算します。
  • 次の値がある場合は、その値で呼び出しaction.acceptて戻りますtrue
  • それ以外の場合は単に戻りますfalse

さらに、あなたはあまり説得力がないように見えることに注意してくださいtrySplit()。どこから始めればよいかさえわかりません。customを継承しAbstractSpliteratorて実装しないほうがよいでしょうtrySplit()。とにかく、あなたの操作は並列実行の恩恵を受けません。そのソースで構築されたストリームは、静かで高価な要素ごとの操作で連鎖する場合にのみ、並列実行から利点を得ることができます。

于 2016-01-14T11:15:20.647 に答える
3

では、スプリッテレータを書きましょう。使い方OfLongはまだ退屈すぎる: に切り替えてBigInteger、user を 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 に答える