Proyecto EULER 25 - Número de Fibonacci de 1000 dígitos -- java campo con performance campo con programming-challenge campo con fibonacci-sequence camp codereview Relacionados El problema

Project Euler 25 - 1000-digit Fibonacci Number


3
vote

problema

Español

He completado recientemente Problema 25 del sitio del Proyecto Euler.

La secuencia FIBONACCI está definida por la relación de recurrencia:

$ qquad f_n = f_ {n-1} + f_ {n-2} $, donde $ f_1 = 1 $ y $ f_2 = 1 $.

Por lo tanto, los primeros 12 términos serán:

$ qquad f_1 = 1 $

$ qquad f_2 = 1 $

$ qquad f_3 = 2 $

$ qquad f_4 = 3 $

$ qquad f_5 = 5 $

$ qquad f_6 = 8 $

$ qquad f_7 = 13 $

$ qquad f_8 = 21 $

$ qquad f_9 = 34 $

$ qquad f_ {10} = 55 $

$ qquad f_ {11} = 89 $

$ qquad f_ {12} = 144 $

El plazo 12, $ F_ {12} $, es el primer término que contiene tres dígitos.

¿Cuál es el primer término en la secuencia FIBONACCI para contener 1000 dígitos?

He resuelto este problema en Java, sin embargo, el tiempo de ejecución es bastante lento y, estoy buscando formas de mejorarlo; A continuación se muestra mi código, así como la salida dada:

  import java.util.ArrayList; import java.math.BigInteger; public class ProjectEuler25 {   public static void main(String [] args) {     long start = System.nanoTime();     ArrayList<BigInteger> fibonacciNumbers = new ArrayList<BigInteger>();     boolean validNo = true;     int x = 2;     BigInteger tempAns = null;     fibonacciNumbers.add(BigInteger.valueOf(1));     fibonacciNumbers.add(BigInteger.valueOf(1));     do {         tempAns = fibonacciNumbers.get(x-1).add(fibonacciNumbers.get(x-2));         fibonacciNumbers.add(tempAns);         x++;         if(tempAns.toString().length() >= 1000) {             validNo = false;         }     } while (validNo == true);     Long stop = System.nanoTime();     System.out.println("The first term in the Fibonacci sequence to contain 1,000 digits is term: " + fibonacciNumbers.size());     System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");   } }   

Salida:

El primer término en la secuencia FIBONACCI para contener 1,000 dígitos es el término: 4782

Tiempo de ejecución: 220.858659 MS

Sé que es posible resolver este problema en C # en 2MS. He proporcionado el código para esta solución a continuación:

  int i = 0; int cnt = 2; BigInteger limit = BigInteger.Pow(10, 999); BigInteger[] fib = new BigInteger[3];  fib[0] = 1; fib[2] = 1;  while (fib[i] <= limit) {     i = (i + 1) % 3;     cnt++;     fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3]; }   

C # Código obtenido de aquí . < / p>

Desde el aspecto del código C #, una cosa que se destaca a mí, es, quizás haya una mejor manera de almacenar los números anteriores que usar un ArrayList ?

Original en ingles

I have recently completed problem 25 from the project Euler site.

The Fibonacci sequence is defined by the recurrence relation:

\$\qquad F_n = F_{nxe2x88x921} + F_{nxe2x88x922}\$, where \$F_1 = 1\$ and \$F_2 = 1\$.

Hence the first 12 terms will be:

\$\qquad F_1 = 1\$

\$\qquad F_2 = 1\$

\$\qquad F_3 = 2\$

\$\qquad F_4 = 3\$

\$\qquad F_5 = 5\$

\$\qquad F_6 = 8\$

\$\qquad F_7 = 13\$

\$\qquad F_8 = 21\$

\$\qquad F_9 = 34\$

\$\qquad F_{10} = 55\$

\$\qquad F_{11} = 89\$

\$\qquad F_{12} = 144\$

The 12th term, \$F_{12}\$, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

I have solved this problem in Java, however, the execution time is fairly slow, and, I am looking for ways to improve it; below is my code, as well as the output given:

import java.util.ArrayList; import java.math.BigInteger; public class ProjectEuler25 {   public static void main(String [] args) {     long start = System.nanoTime();     ArrayList<BigInteger> fibonacciNumbers = new ArrayList<BigInteger>();     boolean validNo = true;     int x = 2;     BigInteger tempAns = null;     fibonacciNumbers.add(BigInteger.valueOf(1));     fibonacciNumbers.add(BigInteger.valueOf(1));     do {         tempAns = fibonacciNumbers.get(x-1).add(fibonacciNumbers.get(x-2));         fibonacciNumbers.add(tempAns);         x++;         if(tempAns.toString().length() >= 1000) {             validNo = false;         }     } while (validNo == true);     Long stop = System.nanoTime();     System.out.println("The first term in the Fibonacci sequence to contain 1,000 digits is term: " + fibonacciNumbers.size());     System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");   } } 

Output:

The first term in the Fibonacci sequence to contain 1,000 digits is term: 4782

Execution time: 220.858659 ms

I know that it is possible to solve this problem in C# in 2ms. I have provided the code for this solution below:

int i = 0; int cnt = 2; BigInteger limit = BigInteger.Pow(10, 999); BigInteger[] fib = new BigInteger[3];  fib[0] = 1; fib[2] = 1;  while (fib[i] <= limit) {     i = (i + 1) % 3;     cnt++;     fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3]; } 

C# code sourced from here.

From looking at the C# code, the one thing which stands out to me, is maybe there is a better way to store the previous numbers than using an ArrayList?

           
         
         

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

TRADURADO EL CÓDIGO DE C # DADO A JAVA, Y TIEMPADO EN MI MÁQUIERA UTILIZANDO EL COMANDO DE UNIX 9988776655544336 . Corrió en 0.161 segundos. Su código original corrió en 1.023 segundos. Aquí está la traducción de Java del código C #:

  import java.math.BigInteger;  public class Euler25 {   public static void main(String[] args) {     int i = 0;     int cnt = 2;     BigInteger limit = (new BigInteger("10")).pow(999);     BigInteger[] fib = new BigInteger[3];      fib[0] = BigInteger.ONE;     fib[2] = BigInteger.ONE;      while ((fib[i]).compareTo(limit) < 0) {         i = (i + 1) % 3;         cnt++;         fib[i] = fib[(i + 1) % 3].add(fib[(i + 2) % 3]);     }     System.out.printf("Fibonacci %d has 1000 digits ", cnt);   } }   

No debe ser excesivamente negativo, pero la solución en el código C # es mucho más limpia que la que implementó. Ninguna pena en eso; Nos pasa a todos. Pero asumo que querías algunos consejos sobre cómo hacer el código que ha corrido más rápido, porque si solo quiere copiar ese C #, usted podría tener fácilmente. Así que esa es la dirección voy a ir con el resto de la respuesta.

Me desconcierta honestamente que este código sea mucho más rápido que el suyo. Habría esperado que las matemáticas Biginteger fueran la parte realmente lenta, pero este código hace la misma cantidad de Matemáticas Biginteger como su código original.

Su código tiene un poco más de memoria, ya que almacena todos los números de Fibonacci que calcula, mientras que este código solo almacena lo que necesita para calcular el siguiente, y usa un entero para contar cuántos números de Fibonacci se ve para lejos. Una lista de matriz está respaldada por una matriz, por lo que en realidad acceder a los artículos no debe ser mucho más lento que con una matriz sencilla, pero podría haber algún tipo de efecto de caché o asignación de memoria. Con este código, el compilador puede bloquear un pedazo de memoria único y estático. En el código original, el ArrayList que almacena los números de Fibonacci se mantiene en expansión, por lo que la matriz de respaldo podría ser reasignada varias veces. Cada vez que se realiza la matriz, todo almacenado en él debe trasladarse al nuevo espacio de almacenamiento, lo que es bastante lento si tiene una lista grande. Si eso resulta ser el problema, puede intentar pasar el constructor 99887776665544339 para BIG, cree que la lista puede obtener ( El tamaño predeterminado es diez ).

Si fuera usted, personificaría el código y buscaría algún problema así. Cavar en la implementación stored >= now0 y vea si está gastando mucho tiempo de reasignación. Solo vea dónde está el código pasando su tiempo, y trata de averiguar por qué es donde está pasando su tiempo. Si aún no tiene un perfilador que le guste, NetBeans tiene una bastante buena incorporada, y estoy seguro de que Eclipse y otros IDES de Java también los tienen. Si presenta perfilando y publica algunos de sus números, probablemente podemos darle una mejor ayuda con el diagnóstico de problemas de rendimiento.

Editar: @Chrishayes descubrió por qué el código es mucho más lento: es el 99887776655443311 Llamar. Tomé el código original y simplemente reemplazé la llamada 99887766655443312 con un cheque sobre un límite de $ 10 ^ 999 $ como lo hace el código C #. Todavía usé la lista de matriz, todavía almacena todos los números de Fibonacci. A medida que Chris Hayes observaba, esto redujo el tiempo de ejecución de aproximadamente 900 ms a aproximadamente 13 ms. El autor de Esta publicación de blog también encontró que stored >= now3 fue bastante lento. Una respuesta en esta página implica que los bigintegers se almacenan de una manera que hace Es más fácil implementar el método stored >= now4 le permite convertir un biginteger en otras bases, como hexadecimal o ternario. Uno aparentemente podría implementar stored >= now5 de una manera más específica que hace que sea rápido convertir en una cadena de base 10, pero difícil o imposible de convertir en cadenas en otras bases, pero los implementadores de la biblioteca estándar eligieron una representación que era más general, pero más lento para convertir en una cadena.

Vea el final de la respuesta para mi versión final del Código, incluidas las modificaciones que hice para deshacerse de stored >= now6 .

[/ editar]

Aparte de los problemas de rendimiento, tuve algunos problemas de legibilidad ", no es que su código fuera ilegible, solo que era más difícil de leer de lo que tenía que ser, y eso contribuyó un poco a la confusión que teníamos sobre dónde había El número 4872 vinaba de. El más grande es la variable stored >= now7 . A menos que esté trabajando con los ejes de coordenadas, no llame a las variables stored >= now8 . El código C # le da la variable análoga el nombre stored >= now9 , que es mejor, ya que puede decir que es probablemente algún tipo de contador. En general, que el código de C # está bastante limpio, por lo que es un buen modelo para aprender, aunque probablemente me gustaría ir todo el camino y llamarlo 99887766555443320 . compareAndSet1 También podría funcionar, ya que es tradicional para indexar los números de Fibonacci con compareAndSet2 . (Esta es otra razón por la que compareAndSet3 es confuso; Si estoy leyendo un programa sobre los números de Fibonacci, puedo procesar 99887766555443324 o el gusto, bastante fácil, pero compareAndSet5 es simplemente extraño.)

También encontré su uso del bucle do-while con una bandera booleana confusa. Un compareAndSet6 o compareAndSet7 bucle con un hubiera sido mejor, pero creo que lo mejor sería dejar que el trabajo hace usted, y escribe algo como esto:

  compareAndSet9  

que aprovecha el hecho de que addAndGet0 se inicializa antes de que se revise la condición del bucle.

El addAndGet11 Clase tiene constantes incorporados para cero y uno, ya que son tan comunes. Para que pueda inicializar su lista de matriz así:

  addAndGet2  

Es un poco más corto que addAndGet3 . (Me gusta Java lo suficientemente bien, pero seguro que puede superarse.)

Aquí está la muestra de código completa con mis cambios sugeridos, incluido el que erradica addAndGet4 y aumenta el rendimiento que Chris Hayes sugirió:

  addAndGet5  

 

I translated the given C# code to Java, and timed it on my machine using the Unix time command. It ran in 0.161 seconds. Your original code ran in 1.023 seconds. Here's the Java translation of the C# code:

import java.math.BigInteger;  public class Euler25 {   public static void main(String[] args) {     int i = 0;     int cnt = 2;     BigInteger limit = (new BigInteger("10")).pow(999);     BigInteger[] fib = new BigInteger[3];      fib[0] = BigInteger.ONE;     fib[2] = BigInteger.ONE;      while ((fib[i]).compareTo(limit) < 0) {         i = (i + 1) % 3;         cnt++;         fib[i] = fib[(i + 1) % 3].add(fib[(i + 2) % 3]);     }     System.out.printf("Fibonacci %d has 1000 digits\n", cnt);   } } 

Not to be excessively negative, but the solution in the C# code is much cleaner than the one you implemented. No shame in that; it happens to all of us. But I assume you wanted some advice on making the code you have run faster, because if you just wanted to copy that C#, you easily could have. So that's the direction I'll go with the rest of the answer.

It honestly puzzles me that this code is so much faster than yours. I would have expected the BigInteger math to be the really slow part, but this code does the same amount of BigInteger math as your original code.

Your code does take quite a bit more memory, since it stores all the Fibonacci numbers it calculates, whereas this code only stores what it needs to calculate the next one, and uses an integer to count how many Fibonacci numbers it's seen so far. An array list is backed by an array, so actually accessing the items shouldn't be much slower than with a plain array, but there might be some kind of cache or memory allocation effect. With this code, the compiler can block out a single, static chunk of memory. In the original code, the ArrayList that stores Fibonacci numbers keeps on expanding, so the backing array might have to be reallocated several times. Every time the array is reallocated, everything stored in it has to be moved over to the new storage space, which is pretty slow if you have a big list. If that turns out to be the problem, you can try passing the ArrayList constructor a guess for big you think the list might get (the default size is ten).

If I were you, I would profile the code and look for some issue like that. Dig into the ArrayList implementation and see if it's spending a lot of time reallocating. Just see where the code is spending its time, and try to figure out why that's where it's spending its time. If you don't already have a profiler you like, Netbeans has a pretty good one built in, and I'm sure Eclipse and other Java IDEs also have them. If you profile and post some of your numbers, we can probably give you better help with diagnosing performance issues.

EDIT: @ChrisHayes discovered why the code is so much slower: it's the toString call. I took the original code and just replaced the toString call with a check against a limit of \$10^999\$ as the C# code does. Still used the array list, still stored all the Fibonacci numbers. As Chris Hayes observed, this reduced the runtime from about 900ms to about 13ms. The author of this blog post also found that BigInteger.toString() was quite slow. An answer on this page implies that BigIntegers are stored in a way that makes it easier to implement the BigInteger.toString(radix) method that lets you convert a BigInteger into other bases, like hexadecimal or ternary. One could apparently implement BigInteger in a more specific way that makes it quick to convert into a base-10 string, but difficult or impossible to convert into strings in other bases, but the standard library implementers chose a representation which was more general, but slower to convert into a string.

See the end of the answer for my final version of the code, including modifications I made to get rid of toString.

[/EDIT]

Aside from the performance issues, I had some readability issuesxe2x80x94not that your code was unreadable, just that it was harder to read than it had to be, and that contributed a little to the confusion that we had over where the number 4872 was coming from. The biggest one is the variable x. Unless you're working with coordinate axes, please don't call variables x. The C# code gives the analogous variable the name cnt, which is better, since you can tell it's probably some kind of counter. In general, that C# code is quite clean, so it's a good model to learn from, though I'd probably just go all the way and call it count. n could also work, since it's traditional to index the Fibonacci numbers with n. (This is another reason why x is confusing; if I'm reading a program about Fibonacci numbers, I can process F_n or the like pretty easily, but F_x is just strange.)

I also found your use of the do-while loop with a boolean flag confusing. A for or while loop with a break statement would have been better, but I think the best would be to let the do-while work for you, and write something like this:

do {     tempAns = fibonacciNumbers.get(n-1).add(fibonacciNumbers.get(n-2));     fibonacciNumbers.add(tempAns);     n++; } while (tempAns.toString().length() < 1000); 

which takes advantage of the fact that tempAns gets initialized before the loop condition is checked.

The BigInteger class has built-in constants for zero and one, since they're so common. So you can initialize your array list like this:

fibonacciNumbers.add(BigInteger.ONE); fibonacciNumbers.add(BigInteger.ONE); 

It's a bit shorter than BigInteger.valueOf(1). (I like Java well enough, but it sure can get long.)

Here's the entire code sample with my suggested changes, including the one that eradicates toString and boosts performance that Chris Hayes suggested:

import java.util.ArrayList; import java.math.BigInteger;  public class ProjectEuler25 {   public static void main(String [] args) {     long start = System.nanoTime();     ArrayList<BigInteger> fibonacciNumbers = new ArrayList<BigInteger>();     int n = 2;  // Index of current Fibonacci number.     BigInteger tempAns = null;     BigInteger limit = new BigInteger("10").pow(999); // First 1000-digit number.      fibonacciNumbers.add(BigInteger.ONE);     fibonacciNumbers.add(BigInteger.ONE);     do {         tempAns = fibonacciNumbers.get(n-1).add(fibonacciNumbers.get(n-2));         fibonacciNumbers.add(tempAns);         n++;     } while (tempAns.compareTo(limit) <= 0);      Long stop = System.nanoTime();     System.out.println("The first term in the Fibonacci sequence " +                        " to contain 1,000 digits is term: " +                         fibonacciNumbers.size());     System.out.println("Execution time: " + ((stop - start) / 1e+6) +                         " ms");   } } 
 
 
   
   

Relacionados problema

3  Implementar el rango de Fibonacci  ( Implement fibonacci range ) 
Estoy implementando una gama FIBONACCI en C ++ 17 de tal manera que admite #include "fib.h" #include <iostream> int main() { for (int x : Fibonacci())...

7  Calcular Fibonacci en O (log n)  ( Calculate fibonacci in olog n ) 
Este programa calcula el número de $ N $ TH FIBONACCI, en el tiempo $ O ( log n) $. Estoy buscando revisión de código, optimizaciones y mejores prácticas....

3  Euler 2: Fibonacci simple  ( Euler 2 simple fibonacci ) 
Estoy empezando a experimentar con F # (desde un fondo C #). Creo que estoy empezando a entrar en la forma de pensar correcta, pero este código todavía parece...

25  Proyecto EULER PROBLEMA 2 EN COTJURE  ( Project euler problem 2 in clojure ) 
Estoy en el proceso de aprendizaje de Clojure. Soy bastante nuevo en la programación funcional y me gustaría saber si mi código huele o si hay alguna implicac...

7  Implementar una secuencia de Fibonacci genérica en óxido sin usar copia rasgo  ( Implement a generic fibonacci sequence in rust without using copy trait ) 
Estoy tratando de aprender a óxido y soy un principiante. ¿Cómo se hace frente a la implementación de una versión genérica de la secuencia FIBONACCI sin usar ...

7  Terminando un bucle C cuando se alcanza el límite máximo de hardware  ( Terminating a c loop when maximum hardware limit reached ) 
en Respuesta a la pregunta C: f & gt; 0 vs perl: $ f & gt; 0? , el uso El desbordamiento para terminar el bucle se conoce como "práctica de programación ...

12  Proyecto EULER # 2 Incluso números de Fibonacci  ( Project euler 2 even fibonacci numbers ) 
Problema: Se genera cada nuevo término en la secuencia Fibonacci al agregar el Dos términos anteriores. Al comenzar con 1 y 2, los primeros 10 términos s...

20  Proyecto EULER # 2 (incluso números de Fibonacci) en Swift  ( Project euler 2 even fibonacci numbers in swift ) 
Pensé que el trabajo a través de Project Euler Problemas en Swift sería una buena manera de aprender cualquier consejo o trucos. Por ejemplo, las tuplas son a...

6  Calculadora de secuencia N-Bonnaci  ( N bonnaci sequence calculator ) 
El código calcula una secuencia N-Bonnaci a un cierto número, según la entrada del usuario. A continuación, puede imprimirlo a un archivo y / o imprimirlo en ...

4  Ruby Fibonacci (n) Cálculo recursivo optimizado con la reflexión  ( Ruby fibonaccin recursive computation optimized with reflection ) 
La idea es tomar el método recursivo de FibonAcci (N) conocido (y terriblemente malo): # recursively computate fibonacci(n) def fib(n) n <= 2 ? 1 : fib(n...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos