How to increase the performance of a recursive method?

Question

I am studying data structures and algorithms, and here is the question that I am stuck with.

I need to improve recursive call performance by storing the value in memory.

But the problem is that not an improved version seems faster than this.

Can someone help me?

Syracus numbers are a sequence of positive integers defined by the following rules:

syra (1) & equiv; 1

syra (n) & equiv; n + syra (n / 2) if n mod 2 == 0

syra (n) & equiv; n + syra ((n * 3) +1), otherwise

import java.util.HashMap; import java.util.Map; public class SyraLengthsEfficient { int counter = 0; public int syraLength(long n) { if (n < 1) { throw new IllegalArgumentException(); } if (n < 500 && map.containsKey(n)) { counter += map.get(n); return map.get(n); } else if (n == 1) { counter++; return 1; } else if (n % 2 == 0) { counter++; return syraLength(n / 2); } else { counter++; return syraLength(n * 3 + 1); } } Map<Integer, Integer> map = new HashMap<Integer, Integer>(); public int lengths(int n) { if (n < 1) { throw new IllegalArgumentException(); } for (int i = 1; i <= n; i++) { syraLength(i); if (i < 500 && !map.containsKey(i)) { map.put(i, counter); } } return counter; } public static void main(String[] args) { System.out.println(new SyraLengthsEfficient().lengths(5000000)); } } 

Here is the normal version I wrote:

  public class SyraLengths{ int total=1; public int syraLength(long n) { if (n < 1) throw new IllegalArgumentException(); if (n == 1) { int temp=total; total=1; return temp; } else if (n % 2 == 0) { total++; return syraLength(n / 2); } else { total++; return syraLength(n * 3 + 1); } } public int lengths(int n){ if(n<1){ throw new IllegalArgumentException(); } int total=0; for(int i=1;i<=n;i++){ total+=syraLength(i); } return total; } public static void main(String[] args){ System.out.println(new SyraLengths().lengths(5000000)); } } 

EDIT

This is slower than the non-extended version.

 import java.util.HashMap; import java.util.Map; public class SyraLengthsEfficient { private Map<Long, Long> map = new HashMap<Long, Long>(); public long syraLength(long n, long count) { if (n < 1) throw new IllegalArgumentException(); if (!map.containsKey(n)) { if (n == 1) { count++; map.put(n, count); } else if (n % 2 == 0) { count++; map.put(n, count + syraLength(n / 2, 0)); } else { count++; map.put(n, count + syraLength(3 * n + 1, 0)); } } return map.get(n); } public int lengths(int n) { if (n < 1) { throw new IllegalArgumentException(); } int total = 0; for (int i = 1; i <= n; i++) { // long temp = syraLength(i, 0); // System.out.println(i + " : " + temp); total += syraLength(i, 0); } return total; } public static void main(String[] args) { System.out.println(new SyraLengthsEfficient().lengths(50000000)); } } 

FINAL DECISION (mark the correct way with the system of automatic marking of the school)

 public class SyraLengthsEfficient { private int[] values = new int[10 * 1024 * 1024]; public int syraLength(long n, int count) { if (n <= values.length && values[(int) (n - 1)] != 0) { return count + values[(int) (n - 1)]; } else if (n == 1) { count++; values[(int) (n - 1)] = 1; return count; } else if (n % 2 == 0) { count++; if (n <= values.length) { values[(int) (n - 1)] = count + syraLength(n / 2, 0); return values[(int) (n - 1)]; } else { return count + syraLength(n / 2, 0); } } else { count++; if (n <= values.length) { values[(int) (n - 1)] = count + syraLength(n * 3 + 1, 0); return values[(int) (n - 1)]; } else { return count + syraLength(n * 3 + 1, 0); } } } public int lengths(int n) { if (n < 1) { throw new IllegalArgumentException(); } int total = 0; for (int i = 1; i <= n; i++) { total += syraLength(i, 0); } return total; } public static void main(String[] args) { SyraLengthsEfficient s = new SyraLengthsEfficient(); System.out.println(s.lengths(50000000)); } 

}

Answer 1

Forget the answers that say that your code is inefficient due to the use of Map , that is not the reason for its slow action - it is the fact that you limit the cache of calculated numbers n < 500 . As soon as you remove this restriction, everything will start working pretty quickly ; here you will be given a confirmation of the concept to fill in the details:

 private Map<Long, Long> map = new HashMap<Long, Long>(); public long syraLength(long n) { if (!map.containsKey(n)) { if (n == 1) map.put(n, 1L); else if (n % 2 == 0) map.put(n, n + syraLength(n/2)); else map.put(n, n + syraLength(3*n+1)); } return map.get(n); } 

If you want to learn more about what's happening in the program and why so fast, take a look at this wikipedia article on Memoization .

In addition, I think that you are using the counter variable incorrectly, you increase it ( ++ ) when the value is calculated for the first time, but you accumulate it ( += ) when the value is found in the map. This does not seem right to me, and I doubt that it gives the expected result.

Answer 2

do not use a card. store a temporary result in a field (it is called a battery) and iterate in a cycle to n = 1. after each cycle, your battery will grow by n. and in each cycle, your n will grow 3 times + 1 or decrease 2 times. Hope that helps you solve your homework.

Answer 3

Of course, this is not so, you add a lot of overhead to the calls to map.put and map.get (hashing, creating a bucket, etc.). In addition, you use autoboxing, which adds to the mess of creating an object. I assume that the overhead of a card far outweighs the benefits.

Try using two arrays instead. one for storing values ​​and for storing flags indicating whether a value is set or not.

 int [] syr = new int[Integer.MAX_VALUE]; boolean [] syrcomputed = new boolean[Integer.MAX_VALUE]; 

and use them instead of the map:

 if (syrcomputed[n]) { return syr[n]; } else { syrcomputed[n] = true; syr[n] = ....; } 

Also, I would think that you might run into some overflow here with large numbers (since syr is approaching MAX_INT / 3, you definitely see this if it is not divisible by 2).

Thus, you should probably use long types for all your calculations.

PS: if your goal is to really understand recursion, you should not store the values ​​as an instance variable, but you should pass it as an accumulator:

 public int syr(int n) { return syr(n, new int[Integer.MAX_VALUE], new boolean[Integer.MAX_VALUE]); } private int syr(int n, int[] syr, boolean[] syrcomputed) { if (syrcomputed[n]) { return syr[n]; } else { s = [ block for recursive computation ] syrcomputed[n] = true; syr = s; } } 

In some functional languages ​​(schema, erlang, etc.), it actually expands as a tail call (which avoids creating a stack). Despite the fact that jvm hotspot does not (at least as far as I know), this is still an important concept.