Header Ads Widget

Ticker

6/recent/ticker-posts

Generando un flujo de números de Fibonacci

 Una secuencia de Java representa potencialmente una secuencia infinita de datos. Esta es una publicación simple que explicará la mecánica involucrada en la generación de un flujo simple de números de Fibonacci .

La forma más sencilla de obtener este flujo de datos es utilizar el
método de generación de Stream .

Como puede imaginar para generar un  número de
Fibonacci específico en esta secuencia, se requieren los dos números anteriores, lo que significa que el estado de los dos números anteriores debe mantenerse en algún lugar. Las dos soluciones que describiré aquí mantienen este estado, sin embargo, lo hacen de manera diferente.

Estado mutable

En el primer enfoque, solo voy a mantener el estado de esta manera:

01
02
03
04
05
06
07
08
09
10
11
12
13
class FibState {
    private long[] prev = new long[2];
    private int index = 0;
 
    public long nextFib() {
        long result = (index == 0) ? 1
                : ((index == 1) ? 1 : prev[0] + prev[1]);
        prev[0] = prev[1];
        prev[1] = result;
        index++;
        return result;
    }
}

con índice que realiza un seguimiento del índice del número de fibonacci actual en la secuencia y prev captura los dos más recientes en la secuencia. Entonces, el siguiente en la serie se genera mutando el índice y cambiando la matriz que contiene los valores recientes. Entonces, dado este estado, ¿cómo generamos la secuencia, usando un código que se ve así:

1
2
3
4
Stream<Long> streamOfFib() {
    FibState fibState = new FibState();
    return Stream.generate(() -> fibState.nextFib());
}

Esto está utilizando un cierre para capturar el estado de fibrilación y mutarlo repetidamente a medida que se genera el flujo de números. El enfoque funciona bien, aunque la idea de mutar un valor probablemente debería inducir un nivel de temor: si es seguro para subprocesos (probablemente no), funcionará para flujos paralelos (probablemente no), pero debería ser suficiente para casos en los que el acceso es estrictamente secuencial. Un enfoque mucho mejor es obtener una versión del estado que sea inmutable.

Estado inmutable

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
18
19
20
21
22
23
class FibState {
    private final long[] prev;
    private final int index;
 
    public FibState() {
        this(new long[]{-1, 1}, 0);
    }
 
    public FibState(long[] prev, int index) {
        this.prev = prev;
        this.index = index;
    }
 
    public FibState nextFib() {
        int nextIndex = index + 1;
        long result = (nextIndex == 1) ? 1 : prev[0] + prev[1];
        return new FibState(new long[]{prev[1], result}, nextIndex);
    }
 
    public long getValue() {
        return prev[1];
    }
}

En lugar de mutar el estado, devuelve el siguiente estado inmutable. Muy bien, ahora que esta versión de estado está disponible, ¿cómo se puede usar? Usando la función
"iterar" de Stream , así:

1
2
3
4
5
Stream<Long> streamOfFib() {
    return Stream
            .iterate(new FibState(), fibState -> fibState.nextFib())
            .map(fibState -> fibState.getValue());
}

esta función toma dos parámetros: el estado inicial y algo que puede generar el siguiente estado. También para devolver números de él, estoy mapeando este tipo de "estado" a un número en la operación de "mapa".

Conclusión

Esto es generalmente instructivo sobre cómo generar una secuencia usando la secuencia de Fibonacci como ejemplo. El enfoque será bastante similar para cualquier flujo que necesite generar. Mi preferencia personal es por la variación de estado inmutable, ya que delega la mayor parte del mecanismo de generación de la secuencia a la excelente función auxiliar "iterar" de la secuencia. 

Publicar un comentario

0 Comentarios