Create an efficient way to summarize

Question

I wrote code to calculate the sum of the lengths in which

syra(1) = 1

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

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

eg.

• syra (1) will generate 1
• syra (2) will generate 2 1
• syra (3) will generate 3 10 5 16 8 4 2 1
• lengths (3) will be the sum of all sira (1), sira (2), sira (3), which is 11.

Here is the code:

 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; } 

Question: if I blew lengths with a large value, for example, 700,000, it will take a very long time and repeat the step for these sire (10), sire (5) ... which already appear in sire (3).

How can I fine tune the code to store some temp (array) overlap sequences?

Well, according to the information, here is my other modified code with an array, why does it give the index of the array from a related 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

Use HashMap<Integer, Integer> to store the results that you have already calculated, and find the values ​​there before trying to recalculate them. This method is known as memoization .

Answer 2

The technique you want to do is called memoization .

You will need to store the output of these smaller calls in some data structure, and then use it instead of calculating again and again.

Suppose you use the LinkedHashMap special constructor with accessOrder=True and overrriden removeEldestEntry () . Read the javadoc LinkedHashMap . It is well described there.

Thus, you can easily save only the very values ​​used and make your cache reasonable (for example, basically 1000 elements).