Programación dinámica con Fibonacci -- java campo con optimization campo con fibonacci-sequence campo con dynamic-programming campo con memoization camp codereview Relacionados El problema

Dynamic programming with Fibonacci


12
vote

problema

Español

He escrito el siguiente código utilizando una técnica de programación dinámica. ¿Puedo usar ArrayList aquí? Por favor, hágamelo saber si puedo mejorar este código.

  #import <Foundation/Foundation.h>  @interface DTMovement : NSObject <NSCoding>  -(id) initWithWorldSize:(CGSize)worldSize;  #pragma mark - Position Properties @property CGPoint currentPosition; @property CGPoint destinationPosition; @property int currentFloor; @property int destinationFloor;  #pragma mark - Update -(void) doMovement;  #pragma mark - Advanced Movement -(void) doIdleMovement; -(void) doVerticalMovement; -(void) doFloorMovement; -(void) pickRandomDestinationOnCurrentFloor;  #pragma mark - Simple Movement -(void) moveUp; -(void) moveDown; -(void) moveLeft; -(void) moveRight;  #pragma mark - Postion Calculations -(int) currentFloorByPosition; -(int) closestFloor:(NSMutableArray *)possibleFloors;  -(void) calculateFloorExitPositionByFloor; -(void) calculateDestinationPositionByFloor;  -(BOOL) isAtVerticalDestinationPosition; -(BOOL) isAtFloorDestinationPosition; -(BOOL) shouldMoveUp; -(BOOL) shouldMoveRight;  #pragma mark - Tower Change -(void) transitionToNewTower;  @end 0  
Original en ingles

I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.

package com.java.fib;  import java.math.BigInteger; import java.util.HashMap;  public class Fibonaci {      public static void main(String[] args) {         System.out.println(" number ");         long startTime = System.currentTimeMillis();         HashMap<Integer, BigInteger> memoized = new HashMap<Integer, BigInteger>();          fibonanci(220, memoized);         System.out.println(" Total Time "                 + (System.currentTimeMillis() - startTime));     }      private static BigInteger fibonanci(int n, HashMap<Integer, BigInteger> memoized) {         if (memoized.containsKey(n)) {             return memoized.get(n);         }         if (n <= 0) {              return BigInteger.ZERO;         }         if (n <= 2) {             return BigInteger.ONE;         } else {             BigInteger  febonani = fibonanci(n - 1, memoized).add (fibonanci(n - 2, memoized));             System.out.println(" febonani " + febonani);                 memoized.put(n, febonani);             return febonani;         }     } } 
              

Lista de respuestas

17
 
vote

Algunas cosas:

Naming:

No es ni Fibonaci , NOR febonani1 , NOR fibonanci Es fibonacci . Por favor, obtenga sus nombres para reflejar lo que realmente está hablando y no es una mutación desfigurada de ella: (

memoized4 OTOH es un nombre relativamente bonito, probablemente prefiero memoizedFibonacciNumbers , pero eso es una cosa de preferencia

Cálculo:

citando wikipedia:

Por definición, los dos primeros números en la secuencia FibonAcci son $ 1 $ y $ 1 $, o $ 0 $ y $ 1 $, dependiendo del punto de inicio elegido de la secuencia, y cada número subsiguiente es la suma de los dos anteriores.

usted por otro lado decir:

El valor de Fibonacci para $ N & LT; = 0 $ es $ 0 $, y para $ n & lt; = 2 $ es $ 1 $, y cada número posterior es la suma de la anterior dos.

Wikipedia también menciona "Números de Fibonacci negativos" . Su definición no coincide con la definición de secuencia Fibonacci real: (

En su lugar, su método FibonAcci debería verse así, si sigue exactamente las reglas para solo números de Fibonacci positivos:

  private static BigInteger fibonacci(Integer n, HashMap<Integer, BigInteger> memoized) {     if (n < 0) {        throw new IllegalArgumentException("We assume the positive Fibonacci sequence only");     }     if (memoized.containsKey(n)) {         return memoized.get(n);     }     if (n == 0) {         memoized.put(n, BigInteger.ZERO);         return memoized.get(n);     }     if (n == 1) {         memoized.put(n, BigInteger.ONE);         return memoized.get(n);     }     BigInteger fibonacci = fibonacci(n-1, memoized).add(fibonacci(n-2, memoized));     memoized.put(n, finbonacci);     return fibonacci; }   

La impresión es lenta :

Te veo que compartimos tu código. Por favor, tenga en cuenta que escribir algo a la consola es bastante lento. Su tiempo de ejecución medido no está coincidiendo con el tiempo de cálculo.

Debe eliminar el System.out.println() en su método FIBONACCI.

Condicionales

También quizás ya se haya dado cuenta, eliminé el else en el método FibonAcci.

Esto se debe a que si su código llega a ese área, todas las demás sucursales han regresado temprano, y el más es bastante inútil.

 

A few things:

Naming:

It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :(

memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference

Calculating:

quoting wikipedia:

By definition, the first two numbers in the Fibonacci sequence are \$1\$ and \$1\$, or \$0\$ and \$1\$, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

You on the other hand say:

The value of Fibonacci for \$n <= 0\$ is \$0\$, and for \$n <= 2\$ is \$1\$, and each subsequent number is the sum of the previous two.

Wikipedia also mentions "negative Fibonacci numbers". Your definition does not match the actual Fibonacci sequence definition :(

instead your fibonacci method should look like this, if you exactly follow the rules for only positive fibonacci numbers:

private static BigInteger fibonacci(Integer n, HashMap<Integer, BigInteger> memoized) {     if (n < 0) {        throw new IllegalArgumentException("We assume the positive Fibonacci sequence only");     }     if (memoized.containsKey(n)) {         return memoized.get(n);     }     if (n == 0) {         memoized.put(n, BigInteger.ZERO);         return memoized.get(n);     }     if (n == 1) {         memoized.put(n, BigInteger.ONE);         return memoized.get(n);     }     BigInteger fibonacci = fibonacci(n-1, memoized).add(fibonacci(n-2, memoized));     memoized.put(n, finbonacci);     return fibonacci; } 

Printing is slow:

I see you benchmarking your code. Please keep in mind, that writing something to the Console is quite slow. Your measured execution time is not matching the calculation time.

You should remove the System.out.println() in your fibonacci method.

Conditionals

Also you maybe have already realized, I removed the else in the fibonacci method.

This is because if your code reaches that area, all other branches have returned early, and the else is quite useless.

 
 
       
       
8
 
vote

@ Vogel612 ya ha mencionado todos los defectos principales y áreas de mejora en su código. Quiero hablar de una cosa más:

Tu paquete Naming es horrible. Está utilizando com.java.fib , no vuelva a hacerlo, porque:

  1. Aunque las clases de Java están prefijadas con febonani0 , todavía crea confusión ya que las personas pueden pensar que esta es una clase de biblioteca. En casos extremos cuando usas nombres profesionales, incluso podría llevar a un nombre de nombre.
  2. Pretendiendo ser o tener algo que ver con febonani1 , que realmente no eres y no.
  3. Cambiarlo a algo imaginario o existente. Use su propio nombre, o su propio sitio web, generalmente uso febonani2 .
  4. Incluso febonani3 sería horrible porque ofrece apenas información adicional, 99887766555443314 no es útil, considere algo a lo largo de las líneas de febonani5 , en el que se puede encontrar la clase febonani6 .
 

@Vogel612 has already mentioned all major defects and areas of improvement in your code. I want to talk about one more thing:

Your package naming is horrible. You are using com.java.fib, please do not ever do that again, because:

  1. Although Java classes are prefixed with java.*, it still creates confusion as people might think this is a library class. In extreme cases when you use professional names, it might even lead to a name clash.
  2. You are pretending to be or have anything to do with java.com, which you really aren't and haven't.
  3. Change it to something imaginary or existing. Use your own name, or your own website, I usually use com.skiwi.*.
  4. Even com.skiwi.fib would be horrible because it offers barely any extra information, com.java.fib.Fibonacci is not helpful, consider something along the lines of com.skiwi.algorithms, in which the class Fibonacci can be found.
 
 
2
 
vote

No use Arraylist. Una búsqueda en la lista con GET (220) lanzará una excepción de índiceOutOfboundSexception. Su lista no se inicializa de forma predeterminada. Lo que puede hacer es usar una matriz para sus valores. Le permite verificar, si ya se llena un índice (VIA! = NULL). Por otro lado, tendrás que predefinir el tamaño de tu matriz. También tendrás que comprobar si también deberá buscar índiceBounds.

  febonani7  
 

Don't use ArrayList. A lookup in the list with get(220) will throw an IndexOutOfBoundsException. Your list is not initialized by default. What you can do is to use an array for your values. It allows you to check, if an index is already filled (via != null). On the other hand, you'll have to predefine the size of your array. Also you'll have to check for indexbounds as well.

public static void main(String[] args) {     final BigInteger[] fibonacciCache = new BigInteger[221];     fibonacciCache[0] = BigInteger.ZERO;     fibonacciCache[1] = BigInteger.ONE;     fibonacci(220, fibonacciCache); }  private static BigInteger fibonacci(int n, final BigInteger[] fibonacciCache) {     if (n<0) n=0;     if (fibonacciCache[n]!=null) {       return fibonacciCache[n];     }     fibonacciCache[n] = fibonacci(n - 1, fibonacciCache).add(fibonacci(n - 2, fibonacciCache));     return fibonacciCache[n]; } 
 
 
2
 
vote

Aparte de las cosas que otras personas han mencionado (lanzando notablemente un error en los números negativos y corrigiendo la ortografía), reordenaría parte de la funcionalidad y agregaría más febonani8 s, así:

  febonani9  

También sugeriría que, en lugar de hacer que el usuario proporcione el hash memoId, usted hace un hash estático privado. Además de hacer menos trabajo para el usuario, esto también le permitiría precargar el hash con los valores de 0, 1 y 2, lo que significa que podría eliminar la lógica de la función y hacerla más sencilla.

  fibonanci0  
 

Aside from the things other people have mentioned (notably throwing an error on negative numbers and correcting the spelling), I would reorder some of the functionality and add more elses like so:

    private static BigInteger fibonacci(int n, HashMap<Integer, BigInteger> memoized)     {             if (n <= 0) {                  return BigInteger.ZERO;             } else if (n <= 2) {                 return BigInteger.ONE;             } else if (memoized.containsKey(n)) {                 return memoized.get(n);             } else {                 BigInteger  result = fibonacci(n - 1, memoized).add (fibonacci(n - 2, memoized));                 memoized.put(n, result);                 return result;             }     } 

I'd also suggest that instead of making the user provide the memoized hash, you instead make a private static hash. Aside from making less work for the user, this would also allow you to preload the hash with the values of 0, 1 and 2, meaning you could strim out some of the function's logic and make it simpler.

    private static HashMap<Integer, BigInteger> memoizedHash;     static     {         memoizedHash = new HashMap<Integer, BigInteger>();         memoizedHash.put(0, BigInteger.ZERO);         memoizedHash.put(1, BigInteger.ONE);         memoizedHash.put(2, BigInteger.ONE);     }     private static BigInteger fibonacci(int n)     {         assert (n >= 0) : "This function does not accept negative numbers";         if (memoizedHash.containsKey(n)) {             return memoizedHash.get(n);         } else {             BigInteger  result = fibonacci(n - 1).add (fibonacci(n - 2));             memoizedHash.put(n, result);             return result;         }     } 
 
 
         
         
0
 
vote

Puede usar ArrayList en lugar de HashMap aquí.

Actualizar:

Después de algunos comentarios, me reemplié el uso de la forma no recursiva, tomó un poco más de más que su código fuente (15 ms en comparación con 11 ms que se ejecutan en mi computadora), pero la mayoría de las veces se gasta para imprimir la salida por 9988776655544332 Función . Hay una pequeña diferencia, agregué 3 primeros números de secuencia de Fibonaci (0, 1, 1) a la matriz de resultados.

  public class Fibonaci {      public static int count = 0;      public static void main(String[] args) {         ArrayList<BigInteger> memoized = new ArrayList<BigInteger>();          long startTime = System.currentTimeMillis();         fibonanci(220, memoized);          for(int i = 0; i < memoized.size(); i++) {             System.out.println(" febonani " + memoized.get(i));         }          System.out.println(" Total Time " + (System.currentTimeMillis() - startTime));     }      private static BigInteger fibonanci(int n, ArrayList<BigInteger> memoized) {         BigInteger febonani = BigInteger.ZERO;         int size = memoized.size();         if (n < 0) {             return BigInteger.ZERO;         }         if (size > n) {                 febonani = memoized.get(n);         } else {             for(int i = size; i <= n; i++) {                 if(i == 0) {                     febonani = BigInteger.ZERO;                 } else if(i == 1 || i == 2) {                     febonani = BigInteger.ONE;                 } else {                     febonani = memoized.get(i - 1).add(memoized.get(i - 2));                 }                 memoized.add(febonani);             }         }         return febonani;     } }   
 

You can use ArrayList instead of HashMap here.

Update:

After some comments, I reimplement using non-recursive way, it took a bit longer than your source code (15 ms in comparison with 11 ms running on my computer), but most of time is spent to print output by System.out.println function. There is a small difference, I added 3 first numbers of Fibonaci sequence (0, 1, 1) to the result array.

public class Fibonaci {      public static int count = 0;      public static void main(String[] args) {         ArrayList<BigInteger> memoized = new ArrayList<BigInteger>();          long startTime = System.currentTimeMillis();         fibonanci(220, memoized);          for(int i = 0; i < memoized.size(); i++) {             System.out.println(" febonani " + memoized.get(i));         }          System.out.println(" Total Time " + (System.currentTimeMillis() - startTime));     }      private static BigInteger fibonanci(int n, ArrayList<BigInteger> memoized) {         BigInteger febonani = BigInteger.ZERO;         int size = memoized.size();         if (n < 0) {             return BigInteger.ZERO;         }         if (size > n) {                 febonani = memoized.get(n);         } else {             for(int i = size; i <= n; i++) {                 if(i == 0) {                     febonani = BigInteger.ZERO;                 } else if(i == 1 || i == 2) {                     febonani = BigInteger.ONE;                 } else {                     febonani = memoized.get(i - 1).add(memoized.get(i - 2));                 }                 memoized.add(febonani);             }         }         return febonani;     } } 
 
 
         
         

Relacionados problema

1  Función de memoiza genérica en Swift  ( Generic memoize function in swift ) 
Necesito realizar un cálculo costoso, como determinar un número de FIBONACCI: /// Calculate the Nth Fibonacci number (inefficiently) func fib(n: Int) -> In...

5  Python: patrón de tarjeta salvaje que coincida con la memoización  ( Python wild card pattern matching with memoization ) 
Aquí está mi opinión sobre el patrón de la tarjeta Wild Tarjeta que coincida con la memoización. Agradecería los comentarios sobre la claridad del Código, a...

8  Generador de caché de Python  ( Python caching generator ) 
¿Es esta la forma correcta de almacenar en caché a un generador en Python, sin la iteración sobre ella de inmediato (por ejemplo, usando 99887776655443316 s...

2  Compruebe la igualdad para cada subconjunto de una cadena S contra la T objetivo y devuelva un conteo  ( Check the equality for each subset of a string s against the target t and return ) 
Escribí el siguiente código para resolver este problema de código de leet : var numDistinct = function(s, t) { if (!s.length) return +(!t.length); ...

7  Clase de ayuda para memorizar a DaDeformats Ancho a toda la aplicación  ( Helper class to memoize dateformats application wide ) 
premisa Considere el siguiente método: static String formatMyDate(Date date) { return new SimpleDateFormat("yyyy-MM-dd").format(date); } A menudo...

5  Levenshtein Distancia con los vectores de Haskell y la memoización  ( Levenshtein distance with haskell vectors and memoization ) 
¿Es la siguiente manera efectiva de implementar la distancia Levenshtein con los vectores de Haskell? n3 En particular, ¿debo usar n4 para construir l...

7  Memoizacion elegante  ( Elegant memoizing ) 
Quería una forma elegante de implementar la memorización. Aquí está lo que he encontrado: JPanel0 Es bastante agradable, pero el mapa débil no está bien...

3  Implementación ingenua de un memoiser de caché menos utilizado (LRU)  ( Naive implementation of a least recently used lru cache memoiser ) 
Escribí código a (ingenuamente) Realizar memoisación de LRU. Intenté escribirlo en un estilo de programación funcional, y así no hizo uso de ninguna variable ...

1  Implementación ingenua de la memorización automática  ( Naive implementation of automatic memoisation ) 
Escribí el código a (ingenuamente) realizar la memorización automática. Intenté escribirlo en un estilo de programación funcional, y así no hizo uso de ningun...

3  decorador de caché  ( Caching decorator ) 
Se me ocurrió un decorador de caché para funciones puras. ¿Está bien? ¿Podría ser mejor / más simple / más rápido? public class Finder { public List<st...




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