Как реализовать Spliterator для потоковой передачи чисел Фибоначчи?
Я играю с 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;
}
}
FibonacciPair:
@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);
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). Возможно, возможна даже более мудрая реализация, которая бы неравномерно использовала промежуточные результаты умножения матриц.
Помимо того факта, что ваш код неполон, есть как минимум две ошибки в вашем tryAdvance Метод узнаваем. Во-первых, вы на самом деле не делаете каких-либо авансов. Вы не изменяете состояние вашего сплитератора. Во-вторых, вы безоговорочно ссылаетесь на действие accept метод, который не соответствует тому факту, что вы возвращаете условное значение, а не true,
Цель tryAdvance является:
- как следует из названия, попробуйте сделать заранее, то есть рассчитать следующее значение
- если есть следующее значение, вызвать
action.acceptс этим значением и возвратомtrue - в противном случае просто вернитесь
false
Обратите внимание, что ваш trySplit() выглядит не очень убедительно, я даже не знаю с чего начать. Вы лучше, наследуя от AbstractSpliterator и не реализуя обычай trySplit(), Ваша операция все равно не выиграет от параллельного выполнения. Поток, созданный из этого источника, может получить преимущество от параллельного выполнения, только если вы объедините его в цепочку тихими дорогими операциями для каждого элемента.
В общем случае вам не нужно реализовывать сплитератор. Если вам действительно нужно 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);
Массив-сплитератор также хорошо разбивается, поэтому у вас будет реальная параллельная обработка.