Fibonacci sequence generation using Java Stream API

_README.md

Fibonacci sequence generation using Java Stream API

Possible solutions and relative performance

Solutions

The generation of a Fibonacci sequence can be carried on in several ways:

• using the generate() method
  • leaning on an external class to keep the state and perform the computation (method fibonacciGG())
  • using a lambda with an external class just to keep the state (method fibonacciGLP())
  • using a lambda storing the state into an external array (method fibonacciGLa())
• using the iterate() method
  • using a lambda with an external class to keep the state (method fibonacciILP())
  • using a lambda with an array to keep the state (method fibonacciILa())
  • using a lambda with an array to keep the state that is re-created at each iteration (method fibonacciILan())

The four implementations are shown in file FibonacciStream.java in the corresponding methods.

Performance

The time performance of the five alternatives above are reported in the following table and illustrated in the diagram.

Solution	Method	Time	Throughput
generate(Generator class)	fibonacciGG()	94.5	106
generate(lambda, array)	fibonacciGLP()	98.5	102
generate(lambda, Pair)	fibonacciGLa()	93.5	107
iterate(lambda, new array)	fibonacciILan()	70.0	143
iterate(lambda, array)	fibonacciILP()	35.0	286
iterate(lambda, Pair)	fibonacciILa()	31.0	323

The performance are based on CPU times collected on a Mac with 2.3 GHz Intel Core i7.

The time measure is the time required to generate a 10M numbers sequence.

The throughput is expressed in Million numbers generated per second.

Conclusions

The two best iterate() solutions outperfom the generate() based solutions by almost three times.

In both cases we observe that the array variants are performing slightly worsed than the ones using an external class. This is likely due to the additional checks performed when accessing an array.

The new array version of the iterate() deserves some additional consideration. It is the solution typically suggested in several places (several stackoverflow answers) as it is the most compact and possibly elegant. Unfortunately it creates a new object every iteration, this solution is inefficient both from a time and memory occupation perspectives.

FibonacciStream.java

package streams;

import java.util.stream.LongStream;
import java.util.stream.Stream;

public class FibonacciStream {
	
	public static LongStream fibonacciGG() {
		class FibonacciGenerator{
			int prev=0;
			int prevPrev=0;
			
			public int next() {
				int result = prev+prevPrev;
				if(prevPrev==0) result=1;
				prevPrev = prev;
				return prev = result;
			}
		}

		FibonacciGenerator g=new FibonacciGenerator();
		return LongStream.generate(g::next);
	}
	
	public static LongStream fibonacciGLa() {
		long[] fibo = {0,0};
		return LongStream.generate(()->{
			long result = fibo[0]+fibo[1];
			if(fibo[1]==0) result=1;
			fibo[1] = fibo[0];
			return fibo[0] = result;
		});
	}

	public static LongStream fibonacciGLP() {
		class Pair{
			long prev;
			long prevPrev;
		}
		Pair fib = new Pair();
		return LongStream.generate(()->{
			long result = fib.prev+fib.prevPrev;
			if(fib.prevPrev==0) result=1;
			fib.prevPrev = fib.prev;
			return fib.prev = result;
		});
	}

	public static LongStream fibonacciILa() {
		return Stream.iterate(new long[] {1,0}, (f)->{
			long result = f[0]+f[1];
			if(f[1]==0) result=1;
			f[1] = f[0];
			f[0] = result;
			return f;
		})
		.mapToLong( f -> f[0]);
	}

	public static LongStream fibonacciILP() {
		class Pair { long pre=1; long prePre=0; }
		return Stream.iterate(new Pair(), (p)->{
			long result = p.pre+p.prePre;
			if(p.prePre==0) result=1;
			p.prePre = p.pre;
			p.pre = result;
			return p;
		})
		.mapToLong( p -> p.pre);
	}
	
	public static LongStream fibonacciILan() {
		return Stream.iterate(new long[] {1,0}, 
				      (f)-> new long[] {f[0]+f[1], f[0]})
		.mapToLong( f -> f[0]);
	}

}

FibonacciStream.svg