Fibonacci sequence methods

Question

Decided to get a little JDK 8 practice in today, so I built two methods to print out the golden ratio, one uses the Stream API the other does not. Wanted to request general feedback on how well I implemented these methods (mainly the stream generator,) considering the given task and if there is anything I could have done better.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * Created on 7/5/2016.
 * 
 */


public class Fibonacci {
    public static void main(String[] args) {
        System.out.printf("Fibonacci Old: %s%n", String.join(", " , Fibonacci.calculateFib(10).stream()
                .map(Object::toString)
                .collect(Collectors.toList())));

        System.out.printf("Fibonacci New: %s%n", String.join(", " , Fibonacci.generateFib()
                .limit(10)
                .map(Object::toString)
                .collect(Collectors.toList())));
    }

    private static List<Integer> calculateFib(int fibCount){
        List<Integer> fibSequence = new ArrayList<>();
        fibSequence.add(0);
        fibSequence.add(1);
        for(int i = 2; i < fibCount; i++){
            fibSequence.add(fibSequence.get(i-1) + fibSequence.get(i-2));
        }
        return fibSequence;
    }

    private static Stream<Integer> generateFib() {
        return Stream.generate(new Supplier<Integer>() {
            List<Integer> list = new ArrayList<>(Arrays.asList(0, 1));
            int i = 0;

            @Override
            public Integer get() {
                list.add(list.get(i) + list.get(i+1));
                return list.get(i++);
            }
        });
    }
}

Answer 1

Collectors.joining

In the two parts of your code, you are using the pattern:

String.join(", " , someStream.map(Object::toString).collect(Collectors.toList()));

to join all the String of a list and separate them with a comma. This has the disadvantage that it requires to construct the whole list in memory only to build the wanted String from it. It would be preferable to use the built-in joining(delimiter) for this task: it will collect the String directly into a String delimited by the given delimiter, without building an intermediate list:

someStream.map(Object::toString).collect(Collectors.joining(", ")));

Stream solution

Your Stream solution has 2 major flaws:

• When run in parallel, it is broken. It is simple to test it: add .parallel() just before returning the Stream inside generateFib() and you will not have the correct result; you may even have an ArrayIndexOutOfBoundsException. Why? generate takes here a Supplier<Integer> that will return the next Integer in the Stream, and in parallel, get() will be invoked concurrently. Unfortunately, its code is not thread-safe, leading to unexpected results / exceptions. You might wonder why this is important: the whole Stream API has been built with the idea that running a pipeline in parallel can be done without effort, by just adding .parallel(), so it would simply be inappropriate to write code that doesn't work in parallel.
• The supplier is storing itself the whole List<Integer> in memory, when in fact, it would only need the last 2 elements to generate the next one.

Using Stream.generate won't do it: it needs state (last 2 values) so we'll never be able to make a parallel-friendly get(): this method is useful to generate inifnite Stream of uncorrelated values, which isn't our case here.

In this case, we can turn to the Stream.iterate method: this method gives us the last element produced to return the next element. So we could have:

private static LongStream generateFib() {
    return Stream.iterate(new long[]{ 0, 1 }, a -> new long[] { a[1], a[0]+a[1] })
                 .mapToLong(a -> a[0]);
}

This creates a Stream of tuples where each tupes is in fact a 2 element array containing the two previous values. It is initialized to the seed of { 0, 1 } and each next value is computed by retuning { p[1], p[0]+p[1] } from an existing tuple. Finally, this Stream is mapped to a LongStream by only keeping the first element of the tuple. (Note that this uses a primitive Stream of long value. It will quickly overflow: using a BigInteger in place of a long is left as exercise for the reader).

The big advantage is that now, you can run this in parallel, and it won't break (not that it would bring any real advantage, one would have to measure for that; a solution that would probably offer better parallel performance would be implementing a custom Spliterator like done on this Stack Overflow answer).

Then

Main.generateFib().limit(10).mapToObj(Long::toString).collect(Collectors.joining(", "))

gives the same output as the initial code.

Answer 2

The "old" method doesn't support a length 0 or 1. It'll always return at least 2 elements, so maybe you should add a special case for that?

You ought to write out your method names in full - generateFib is pretty unclear in meaning, unless you're generating lies.

I also notice that...

private static List<Integer> calculateFib(int fibCount){
    List<Integer> fibSequence = new ArrayList<>();

You know how long the list is going to be, so why not ensure the capacity beforehand with new ArrayList<>(fibCount);?

Aside from that, there's really not much to say about such a short implementation.