Optimización de procesos con Programación Funcional.

En los post anteriores hemos visto qué es la programación funcional y cómo podemos mejorar nuestro código usándola. En este post vamos a ver cómo optimizar los procesos usando programación funcional.

El ejemplo por excelencia de la recursividad es devolver el número N de la sucesión Fibonacci. Veamos cómo se puede hacer en Java:

public long fibonacci (int n)
{
    if ((n == 1) || (n == 2)) {
        return 1;
    }
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Ya tenemos nuestro generador de números de Fibonacci. Vamos a generar unos cuantos:

long n = fibonacci(5);
System.out.print(n);
n = fibonacci(10);
System.out.println(n);
n = fibonacci(20);
System.out.println(n);

Este código funciona y nos devuelve los números, pero tiene un problema en cuanto empezamos a buscar números más altos. Por ejemplo este código:

LocalTime start = LocalTime.now();
long n = fibonacci(45);
long millis = start.until(LocalTime.now(), ChronoUnit.MILLIS);
System.out.println(String.format("Valor %d calculado en %d milisegundos", n, millis));

Devuelve esto:

Valor 1134903170 calculado en 3499 milisegundos

Puede que 3 segundos no sean nada para ti, pero en cuanto busques alguno un poco más alto nos vamos a tiempos inmanejables. Para el valor 50 tarda unos 39 segundos en mi portátil (un Macbook Pro con procesador i7).

El fallo de este código es que las llamadas al stack aumentan y por eso cada vez se vuelve más lento, además de que podemos tener un StackOverflowError si pedimos números más altos.
Lo primero que hay que hacer es que nuestro método sea Tail Recursive. Las funciones son tail recursive cuando la llamada a la recursión se hace en la última línea del método. Esto hace que se optimicen las llamadas en el stack y el resultado sea más rápido. Veamos cómo cambiar nuestro código para conseguirlo:

public long fibonacci(int n) {
    return f(1, 0, n);
}
private long f(long acc1, long acc2, long x) {
    if (x == 0) {
        return 1;
    } else if (x == 1) {
        return acc1 + acc2;
    } else {
        return f(acc2, acc1 + acc2, x - 1);
    }
}

Si probamos el código nuevo pasándole el 1000 tarda... ¡unos 8 milisegundos! Ahora veremos cómo podemos mostrar todos los números hasta un número dado en la sucesión de Fibonacci:

LocalTime start = LocalTime.now();
int serie = 10;
String result = IntStream.rangeClosed(1, serie)
        .boxed()
        .map(n -> String.valueOf(fibonacci(n)))
        .collect(Collectors.joining(","));
long millis = start.until(LocalTime.now(), ChronoUnit.MILLIS);
System.out.println(String.format("Serie Fibonacci del 1 al %d generada en %d milisegundos", serie, millis));
System.out.println(result);

Usamos un IntStream para llamar n veces a la función y obtener la serie. El resultado es el siguiente:

Serie Fibonacci del 1 al 10 generada en 19 milisegundos
1,1,2,3,5,8,13,21,34,55

Veamos lo mismo para el 10000:

Serie Fibonacci del 1 al 10000 generada en 230 milisegundos
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584, …

Parece bastante óptimo, 230 milisegundos es un tiempo razonable, pero aún hay un problema, y es que para generar los número hay que llamar muchas veces a la función f, en concreto para esta generación se le llama 50005000 veces. Si queremos volver a generarlos tendremos que repetir el proceso entero sabiendo que el resultado será el mismo, algo que no tiene mucho sentido. La forma para hacer que este código mejore es usar la memoización.

La memoización es el proceso por el que cacheamos los resultados de las funciones para devolverlos sin computarlos otra vez. Esto solo se puede hacer cuando estamos usando funciones puras, que son aquellas que siempre devuelven el mismo resultado para la misma entrada y que no tienen efectos de lado, es decir, que no cambian otras variables o escriben a disco, a consola, etc... Este es uno de los pilares de la programación funcional, la inmutabilidad del código.

Vamos a cambiar nuestra función de la siguiente manera añadiendo una función de memoización:

private Map<Integer, Long> memory = new ConcurrentHashMap<>();
public long fibonacci(int n) {
    return memory.computeIfAbsent(n, x -> f(1, 0, x));
}

Y nuestra llamada ahora la haremos dos veces para ver si los resultados son mejores:

int serie = 10000;
LocalTime start = LocalTime.now();
String result = IntStream.rangeClosed(1, serie)
        .boxed()
        .map(n -> String.valueOf(fibonacci(n)))
        .collect(Collectors.joining(","));
long millis = start.until(LocalTime.now(), ChronoUnit.MILLIS);
System.out.println(String.format("Serie Fibonacci del 1 al %d generada en %d milisegundos", serie, millis));
System.out.println(result);
start = LocalTime.now();
result = IntStream.rangeClosed(1, serie)
        .boxed()
        .map(n -> String.valueOf(fibonacci(n)))
        .collect(Collectors.joining(","));
millis = start.until(LocalTime.now(), ChronoUnit.MILLIS);
System.out.println(String.format("Serie Fibonacci regenerada del 1 al %d generada en %d milisegundos", serie, millis));
System.out.println(result);

Esta es la salida:

Serie Fibonacci del 1 al 10000 generada en 230 milisegundos
1,1,2,3,5,8,13,21,34,55,89,144,233,377
Serie Fibonacci regenerada del 1 al 10000 generada en 11 milisegundos
1,1,2,3,5,8,13,21,34,55,89,144,233,377

La primera vez que llamamos a la función tarda lo mismo que antes ya que tiene que generar todos los resultados, pero la segunda vez solo tarda 11 milisegundos gracias a que la computación ya no es necesaria al estar cacheada.

Y por último, como colofón, tenemos la forma más simple y la que ofrece un mayor rendimiento. Se trata de crear un Stream infinito gracias a la evaluación perezosa (lazy) de la que Java 8 nos provee.

Lo primero es crear una clase donde almacenaremos nuestras tuplas con el índice y el resultado en la sucesión:

public class Tuple2<T, U> {
    public final T _1;
    public final U _2;
    public Tuple2(T t, U u) {
        this._1 = t;
        this._2 = u;
    }
}

Si conoces Scala estarás familiarizado con esta clase. Para implementar el resto del código vamos a usar Streams y operadores unarios:

Tuple2<Long, Long> seed = new Tuple2<>(1L, 1L);
UnaryOperator<Tuple2<Long, Long>> f = x -> new Tuple2<>(x._2, x._1 + x._2);
int serie = 10000;
LocalTime start = LocalTime.now();
Stream<Long> fibonacciStream = Stream.iterate(seed, f)
        .map(x -> x._1)
        .limit(serie);
String result = fibonacciStream.map(Object::toString).collect(Collectors.joining(", "));
long millis = start.until(LocalTime.now(), ChronoUnit.MILLIS);
System.out.println(String.format("Serie Fibonacci del 1 al %d generada en %d milisegundos", serie, millis));
System.out.println(result);

Con este código generamos un stream infinito de esta forma:

(1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), ...

Si ejecutamos el código lo que vemos es:

Serie Fibonacci del 1 al 10000 generada en 18 milisegundos
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Lo más importante a parte del rendimiento es que ahora solo llamamos a nuestra función n - 1 veces, donde n es último número de la sucesión que queremos sacar. Para este caso habríamos llamado a la función 9999 veces haciendo nuestro código 10 veces más rápido que con la primera forma.

La programación funcional no siempre es efectiva para optimizar todos los algoritmos, pero en el caso de algoritmos recursivos es muy efectiva. Cada algoritmo es un mundo y tendrás que valorar qué tipo de optimización hacer según el caso.

De todas maneras, ahora ya tienes otra formas de hacer tu código. Recuerda que un código que compila y pasa los tests no siempre significa que sea el más óptimo.