sobre - imagenes java eclipse

Haciendo Fibonacci más rápido

Question

Esta pregunta ya tiene una respuesta aquí:

• enésimo número de fibonacci en tiempo sublineal 13 respuestas

Se me pidió que escribiera una implementación simple del algoritmo de Fibonacci y luego la hiciera más rápida .

Aquí está mi implementación inicial

public class Fibonacci {
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return getFibonacciOf(n-2) + getFibonacciOf(n-1);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
}

Como puede ver, estoy usando System.currentTimeMillis () para obtener una medida simple del tiempo transcurrido mientras calculaba Fibonacci.

Esta implementación se vuelve rápidamente más lenta de manera exponencial como se puede ver en la siguiente imagen

Así que tengo una idea de optimización simple. Para poner los valores anteriores en un HashMap y en lugar de volver a calcularlos cada vez, simplemente retíralos de HashMap si existen. Si no existen, los colocamos en el HashMap .

Aquí está la nueva versión del código

public class FasterFibonacci {
private static Map<Long, Long> previousValuesHolder;
static {
previousValuesHolder = new HashMap<Long, Long>();
previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
}
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (previousValuesHolder.containsKey(Long.valueOf(n))) {
return previousValuesHolder.get(n);
} {
long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
previousValuesHolder.put(Long.valueOf(n), Long.valueOf(newValue));
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}

Este cambio hace que la computación sea extremadamente rápida. Calculo todos los valores de 2 a 103 en poco tiempo y obtengo un desbordamiento largo en F (104) ( Me da F (104) = -7076989329685730859, lo cual es incorrecto ). Lo encuentro tan rápido que ** Me pregunto si hay algún error en mi código (gracias su comprobación y hágamelo saber por favor) **. Por favor, eche un vistazo a la segunda imagen:

¿Es correcta la implementación del algoritmo de mi fibonacci más rápido (me parece que lo es porque tiene los mismos valores que la primera versión, pero como la primera versión era demasiado lenta, no pude calcular valores más grandes como F (75))? ¿Qué otra manera puedo usar para hacerlo más rápido? ¿O hay una mejor manera de hacerlo más rápido? Además, ¿cómo puedo calcular Fibonacci para obtener valores mayores (como 150, 200) sin obtener un ** desbordamiento largo **? Aunque parece rápido, me gustaría llevarlo al límite. Recuerdo que el Sr. Abrash dijo " El mejor optimizador está entre tus dos oídos ", así que creo que todavía se puede mejorar. Gracias por ayudar

[Nota de la edición:] Aunque esta pregunta aborda uno de los puntos principales de mi pregunta, puede ver desde arriba que tengo problemas adicionales.

Answer 1

Programación dinámica

Idea: en lugar de volver a calcular el mismo valor varias veces, simplemente almacena el valor calculado y úselo a medida que avanza.

f(n)=f(n-1)+f(n-2) con f (0) = 0, f (1) = 1. Entonces, en el momento en que haya calculado f (n-1), puede calcular fácilmente f (n) si almacena los valores de f (n) yf (n-1).

Tomemos una serie de Bignums primero. A [1..200]. Inicialízalos a -1.

Pseudocódigo

fact(n)
{
if(A[n]!=-1) return A[n];
A[0]=0;
A[1]=1;
for i=2 to n
A[i]= addition of A[i],A[i-1];
return A[n]
}

Esto se ejecuta en tiempo O (n) . Compruébalo tú mismo.

Esta técnica también se llama memoización .

La idea

La programación dinámica (generalmente denominada DP) es una técnica muy poderosa para resolver una clase particular de problemas. Exige una formulación muy elegante del enfoque y el pensamiento simple y la parte de codificación es muy fácil. La idea es muy simple. Si resolvió un problema con la entrada dada, guarde el resultado para futuras referencias, para evitar volver a resolver el mismo problema ... en breve "Recuerde su pasado".

Si el problema dado se puede dividir en subproblemas más pequeños y estos subproblemas más pequeños se dividen a su vez en otros aún más pequeños, y en este proceso, si observa algunos over-lappping subproblems , entonces es una gran sugerencia para DP . Además, las soluciones óptimas para los subproblemas contribuyen a la solución óptima del problema dado (denominado Optimal Substructure Property ).

Hay dos maneras de hacer esto.

1.) De arriba a abajo: Comience a resolver el problema dado desglosándolo. Si ve que el problema ya se ha resuelto, simplemente devuelva la respuesta guardada. Si no se ha resuelto, resuélvelo y guarde la respuesta. Esto suele ser fácil de pensar y muy intuitivo. Esto se conoce como memoización. (He usado esta idea).

2.) De abajo hacia arriba: analice el problema y vea el orden en que se resuelven los subproblemas y comience a resolver desde el subproblema trivial, hacia el problema dado. En este proceso, se garantiza que los subproblemas se resuelven antes de resolver el problema. Esto se conoce como programación dinámica . ( MinecraftShamrock utilizó esta idea)

¡Hay más!

(Otras formas de hacer esto)

Mira nuestra búsqueda para obtener una mejor solución no termina aquí. Verás un enfoque diferente

Si sabes cómo resolver recurrence relation entonces encontrarás una solución a esta relación

f(n)=f(n-1)+f(n-2) given f(0)=0,f(1)=1

Llegará a la fórmula después de resolverlo-

f(n)= (1/sqrt(5))((1+sqrt(5))/2)^n - (1/sqrt(5))((1-sqrt(5))/2)^n

Que se puede escribir en forma más compacta.

f(n)=floor((((1+sqrt(5))/2)^n) /sqrt(5) + 1/2)

Complejidad

Puede obtener la potencia de un número en operaciones O (logn) . Tienes que aprender la Exposiciónción por cuadratura .

EDITAR : Es bueno señalar que esto no significa necesariamente que el número de fibonacci se puede encontrar en O (logn). En realidad, la cantidad de dígitos que necesitamos para calcular las líneas lineales. Probablemente debido a la posición en la que afirmé que parece afirmar la idea errónea de que el factorial de un número se puede calcular en tiempo O (logn). [Bakurui, MinecraftShamrock comentó esto]

Answer 2

Alejarse de la recursión de Fibonacci y usar las identidades.

(F(2n), F(2n-1)) = (F(n)^2 + 2 F(n) F(n-1), F(n)^2+F(n-1)^2)
(F(2n+1), F(2n)) = (F(n+1)^2+F(n)^2, 2 F(n+1) F(n) - F(n)^2)

Esto le permite calcular (F (m + 1), F (m)) en términos de (F (k + 1), F (k)) para k la mitad del tamaño de m. Escrito de forma iterativa con algunos cambios de bits para la división por 2, esto debería proporcionarle la velocidad teórica O (log n) de la exponenciación al cuadrar mientras se mantiene completamente dentro de la aritmética de enteros. (Bueno, operaciones aritméticas O (log n). Dado que trabajará con números con aproximadamente n bits, no será el tiempo O (log n) una vez que se haya forzado a cambiar a una biblioteca entera grande. Después de F (50) ), desbordará el tipo de datos enteros, que solo sube a 2 ^ (31).

(Disculpas por no recordar Java lo suficientemente bien como para implementarlo en Java; cualquiera que lo desee es libre de editarlo).

Answer 3

Aquí hay una forma de hacerlo de manera demostrable en O (log n ) (ya que el ciclo se ejecuta log n veces):

/*
* Fast doubling method
* F(2n) = F(n) * (2*F(n+1) - F(n)).
* F(2n+1) = F(n+1)^2 + F(n)^2.
* Adapted from:
* https://www.nayuki.io/page/fast-fibonacci-algorithms
*/
private static long getFibonacci(int n) {
long a = 0;
long b = 1;
for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
long d = a * ((b<<1) - a);
long e = (a*a) + (b*b);
a = d;
b = e;
if (((n >>> i) & 1) != 0) {
long c = a+b;
a = b;
b = c;
}
}
return a;
}

Estoy asumiendo aquí (como es convencional) que una operación de multiplicación / adición / lo que sea es tiempo constante independientemente del número de bits, es decir, que se utilizará un tipo de datos de longitud fija.

Esta página explica varios métodos de los cuales este es el más rápido. Simplemente lo traduje del uso de BigInteger para BigInteger lectura. Aquí está la versión de BigInteger :

/*
* Fast doubling method.
* F(2n) = F(n) * (2*F(n+1) - F(n)).
* F(2n+1) = F(n+1)^2 + F(n)^2.
* Adapted from:
* http://www.nayuki.io/page/fast-fibonacci-algorithms
*/
private static BigInteger getFibonacci(int n) {
BigInteger a = BigInteger.ZERO;
BigInteger b = BigInteger.ONE;
for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
BigInteger d = a.multiply(b.shiftLeft(1).subtract(a));
BigInteger e = a.multiply(a).add(b.multiply(b));
a = d;
b = e;
if (((n >>> i) & 1) != 0) {
BigInteger c = a.add(b);
a = b;
b = c;
}
}
return a;
}

Answer 4

Aquí se corta el código con enfoque iterativo en lugar de recursión.

Ejemplo de salida :

Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 5,718 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 0 milliseconds

Algunas partes de los resultados se omiten con ... para una mejor visualización.

Fragmento de código :

public class CachedFibonacci {
private static Map<BigDecimal, BigDecimal> previousValuesHolder;
static {
previousValuesHolder = new HashMap<>();
previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
}
public static BigDecimal getFibonacciOf(long number) {
if (0 == number) {
return BigDecimal.ZERO;
} else if (1 == number) {
return BigDecimal.ONE;
} else {
if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
return previousValuesHolder.get(BigDecimal.valueOf(number));
} else {
BigDecimal olderValue = BigDecimal.ONE,
oldValue = BigDecimal.ONE,
newValue = BigDecimal.ONE;
for (int i = 3; i <= number; i++) {
newValue = oldValue.add(olderValue);
olderValue = oldValue;
oldValue = newValue;
}
previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.print("Enter n: ");
long inputNumber = scanner.nextLong();
if (inputNumber >= 0) {
long beginTime = System.currentTimeMillis();
BigDecimal fibo = getFibonacciOf(inputNumber);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds/n", inputNumber, fibo, delta);
} else {
System.err.println("You must enter number > 0");
System.out.println("try, enter number again, please:");
break;
}
}
}
}

Este enfoque se ejecuta mucho más rápido que la versión recursiva.

En tal situación, la solución iterativa tiende a ser un poco más rápida, porque cada llamada de método recursivo requiere una cierta cantidad de tiempo de procesador. En principio, es posible que un compilador inteligente evite las llamadas a métodos recursivos si siguen patrones simples, pero la mayoría de los compiladores no lo hacen. Desde ese punto de vista, es preferible una solución iterativa.

Answer 5

Habiendo seguido un enfoque similar hace algún tiempo, me he dado cuenta de que hay otra optimización que puede hacer.

Si conoce dos respuestas consecutivas grandes, puede usar esto como punto de partida. Por ejemplo, si conoce F (100) y F (101) , entonces calcular F (104) es aproximadamente tan difícil (*) como calcular F (4) basándose en F (0) y F (1) .

Calcular de manera iterativa es tan eficiente en cuanto a los cálculos como hacer lo mismo usando la recursión en caché, pero usa menos memoria.

Después de haber hecho algunas sumas, también me he dado cuenta de que, para cualquier z < n dado:

F (n) = F (z) * F (nz) + F (z-1) * F (nz-1)

Si n es impar, y elige z=(n+1)/2 , esto se reduce a

F (n) = F (z) ^ 2 + F (z-1) ^ 2

Me parece que deberías poder usar esto con un método que aún tengo que encontrar, que deberías poder usar la información anterior para encontrar F (n) en el número de operaciones igual a:

el número de bits en n duplicaciones (como arriba) + el número de 1 bits en n agregados; en el caso de 104, esto sería (7 bits, 3 ''1'' bits) = 14 multiplicaciones (escuadrados), 10 adiciones.

(*) Suponiendo que sumar dos números lleva el mismo tiempo, independientemente del tamaño de los dos números.

Answer 6

Precalcular una gran cantidad de resultados de fib(n) y almacenarlos como una tabla de búsqueda dentro de su algoritmo. Bam, "velocidad" libre

Ahora, si necesita calcular fib(101) y ya tiene fibs de 0 a 100 almacenadas, esto es como tratar de calcular fib(1) .

Lo más probable es que esto no sea lo que esta tarea está buscando, pero es una estrategia completamente legítima y, básicamente, la idea del almacenamiento en caché se extrajo aún más de ejecutar el algoritmo. Si sabes que es probable que estés calculando las primeras 100 fibs a menudo y necesites hacerlo muy rápido, no hay nada más rápido que O (1). Así que calcule esos valores completamente fuera de banda y guárdelos para que puedan ser buscados más tarde.

Por supuesto, los valores de caché también los calculan :) El cómputo duplicado es desperdicio.

Answer 7

Si necesita calcular con mucha frecuencia los números de fibonacci, sugiero usar la respuesta de amalsom.

Pero si quiere calcular un número de Fibonacci muy grande, se quedará sin memoria porque está almacenando todos los números de Fibonacci más pequeños. El siguiente pseudocódigo solo conserva los dos últimos números de Fibonacci en la memoria, es decir, requiere mucha menos memoria:

fibonacci(n) {
if n = 0: return 0;
if n = 1: return 1;
a = 0;
b = 1;
for i from 2 to n: {
sum = a + b;
a = b;
b = sum;
}
return b;
}

Análisis
Esto puede calcular números muy altos de fibonacci con un consumo de memoria bastante bajo: tenemos O (n) tiempo mientras el bucle se repite n-1 veces. La complejidad del espacio también es interesante: el número n de fibonacci tiene una longitud de O (n), que se puede mostrar fácilmente:
F _n <= 2 * F _n-1
Lo que significa que el número n de fibonacci es a lo sumo el doble de grande que su predecesor. Duplicar un número en binario es equivalente con un único desplazamiento hacia la izquierda, lo que aumenta la cantidad de bits necesarios en uno. Entonces, representar el enésimo número de fibonacci requiere como máximo O (n) espacio. Tenemos como máximo tres números de fibonacci sucesivos en la memoria, lo que hace que O (n) + O (n-1) + O (n-2) = O (n) consumo total de espacio . En contraste con esto, el algoritmo de memorización siempre mantiene los primeros n números de fibonacci en la memoria, lo que hace que O (n) + O (n-1) + O (n-2) + ... + O (1) = O (n ^ 2) consumo de espacio

Entonces, ¿de qué manera se debe usar?
La única razón para mantener todos los números de fibonacci más bajos en la memoria es si necesita números de fibonacci con mucha frecuencia. Se trata de equilibrar el tiempo con el consumo de memoria.

Answer 8

• Fibonacci (0) = 0
• Fibonacci (1) = 1
• Fibonacci (n) = Fibonacci (n - 1) + Fibonacci (n - 2), cuando n> = 2

Por lo general, hay 2 formas de calcular el número de Fibonacci:

1. Recursion

   public long getFibonacci(long n) {
   if(n <= 1) {
   return n;
   } else {
   return getFibonacci(n - 1) + getFibonacci(n - 2);
   }
   }

   De esta manera es intuitivo y fácil de entender, mientras que debido a que no reutiliza el número de Fibonacci calculado, la complejidad del tiempo es aproximadamente O(2^n) , pero no almacena el resultado calculado, por lo que ahorra mucho espacio, en realidad la complejidad del espacio es O(1) .

2. Programación dinámica :

   public long getFibonacci(long n) {
   long[] f = new long[(int)(n + 1)];
   f[0] = 0;
   f[1] = 1;
   for(int i=2;i<=n;i++) {
   f[i] = f[i - 1] + f[i - 2];
   }
   return f[(int)n];
   }

   Esta forma de Memoization calculó los números de Fibonacci y los reutilizó al calcular el siguiente. La complejidad del tiempo es bastante buena, que es O(n) , mientras que la complejidad del espacio es O(n) . Investiguemos si la complejidad del espacio se puede optimizar ... Dado que f(i) solo requiere f(i - 1) y f(i - 2) , no es necesario almacenar todos los números de Fibonacci calculados.

   La implementación más eficiente es :

   public long getFibonacci(long n) {
   if(n <= 1) {
   return n;
   }
   long x = 0, y = 1;
   long ans;
   for(int i=2;i<=n;i++) {
   ans = x + y;
   x = y;
   y = ans;
   }
   return ans;
   }

   Con la complejidad del tiempo O(n) y la complejidad del espacio O(1) .

Agregado: Dado que el número de Fibonacci aumenta increíblemente rápido, long solo puede manejar menos de 100 números de Fibonacci. En Java, podemos usar BigInteger para almacenar más números de Fibonacci.