Crear una forma eficiente para resumir

Question

he escrito un código para calcular la suma de las longitudes cual

syra(1) = 1

syra(2) = n + syra(n/2) if n%2==0

syra(3) = n + (n*3) + 1

por ejemplo.

• syra (1) generará 1
• syra (2) generará 2 1
• syra (3) generará 3 10 5 16 8 4 2 1
• longitudes (3) serán suma de todos syra (1), syra (2), syra (3), que es 11.

Aquí está el código:

public static int lengths(int n) throws IllegalArgumentException{ 
    int syra = n; 
    int count = 0;  
    int sum = 0; 
    if (syra < 1){ 
    throw new IllegalArgumentException("Value must be greater than 0"); 
    }else{ 
    for (int i=1; i<=syra; i++){ 
     count = i; 
     sum++; 
     while (count > 1){ 
     if ((count % 2) == 0){ 
      count = count/2; 
      sum++; 
     }else{ 
      count = (count * 3) + 1; 
      sum++; 
     } 
     } 
    } 
    } 
    return sum; 
} 

La pregunta es, si exploto las longitudes con un gran valor, por ejemplo, 700000, tomará mucho tiempo y repetiré el paso para aquellas syra (10), syra (5) ... que ya aparecen en syra (3).

¿Cómo puedo afinar el código para almacenar algunas temp (matriz) de las secuencias de superposición?

Ok, de acuerdo con la información, aquí está mi otro código modificado con array, ¿por qué produce un índice de matriz sin error?

public class SyraLengths{ 

public static void main (String[]args){ 
    lengths(3); 
} 

public static int lengths(int n) throws IllegalArgumentException{ 
    int syra = n; 
    int count = 0; 
    int sum = 0; 
    int [] array = new int [syra+1]; 
    array[0] = 0; 
    if (syra < 1){ 
     throw new IllegalArgumentException("Value must be greater than 0"); 
     }else{ 


       for (int i=1; i<=syra; i++){ 
        count = i; 
        sum++; 

        while (count > 1){ 

         if(array[count] !=0){sum = sum + array[count];} 

         else if ((count % 2) == 0){ 
          count = count/2; 
          array[count]=sum; 
          sum++; 
         }else{ 
          count = (count * 3) + 1; 
          array[count]=sum; 
          sum++; 

          } 
         } 
       } 
      }return sum; 
} 

}

Answer 1

Utilice un HashMap<Integer, Integer> para almacenar los resultados que ya se han computado, y buscar valores no antes de intentar volver a calcular ellos. Esta técnica se conoce como memoization.

Answer 2

La técnica que desea hacer se llama memoization.

Deberá almacenar la salida de esas llamadas más pequeñas en alguna estructura de datos y luego usarla en lugar de calcular una y otra vez.

Considere usar el constructor especial LinkedHashMap con accessOrder=True y el método removeEldestEntry() overrriden. Lea el javadoc LinkedHashMap. Está bien descrito allí.

Al hacerlo, puede guardar fácilmente solo aquellos valores más utilizados y mantener su caché razonablemente pequeño (es decir, 1000 elementos utilizados en su mayoría).