Java에서 Collatz 추측 최적화

Question

Collatz 추측을 사용하여 숫자가 1이되는 데 걸리는 단계 수를 결정하는 프로그램에서 작업하고 있습니다 (n이 홀수이면 3n + 1, n이 짝수이면 n/2). 이 프로그램은 계산을 완료 할 때마다 계산되는 숫자를 하나씩 늘리고 초 단위로 계산할 수있는 숫자의 수를 테스트합니다. 여기에 내가 현재 가지고 작업 프로그램 :

public class Collatz { 
    static long numSteps = 0; 
    public static long calculate(long c){ 
     if(c == 1){ 
      return numSteps; 
     } 
     else if(c % 2 == 0){ 
      numSteps++; 
      calculate(c/2); 
     } 
     else if(c % 2 != 0){ 
      numSteps++; 
      calculate(c * 3 + 1); 
     } 
     return numSteps; 
    } 
    public static void main(String args[]){ 
     int n = 1; 
     long startTime = System.currentTimeMillis(); 
     while(System.currentTimeMillis() < startTime + 60000){ 

      calculate(n); 
      n++; 
      numSteps = 0; 
     } 
     System.out.println("The highest number was: " + n); 
    } 
} 

그것은 현재 분에서 1 억 번호를 계산할 수는 있지만, 나는 더는 더 많은 숫자를 계산할 수 있도록 프로그램을 최적화하는 방법에 대한 조언을 찾고 있어요 1 분. 모든 조언을 부탁드립니다 :).

Answer 1

당신은 그 c % 2 == 0입니다 가정에 의한 계산 방법은 c % 2 != 0보다 거짓

• 최적화가 참이어야 수 있습니다. c * 3 + 1은 짝수 여야한다고 가정하여 (c * 3 + 1)/2을 계산하고 numSteps에 2를 더할 수 있습니다. 자바가 꼬리 - 호출 최적화를 가지지 않기 때문에 재귀 대신 루프를 사용할 수 있습니다.

• 기억을 사용하면 더 큰 개선 효과를 얻을 수 있습니다. 각 각 숫자에 대해 얻은 결과와 그 값을 반환하기 전에 계산 된 숫자를 암기 할 수 있습니다. 예를 들어 암기에 상한을 두는 것이 좋습니다. 계산하려는 마지막 숫자보다 높지 않아야합니다. 이 값을 사용하지 않으면 가장 큰 값의 몇 배가됩니다. 더 고급 대답이 될 것이다 관심을

public class Collatz { 
    static final int[] CALC_CACHE = new int[2_000_000_000]; 

    static int calculate(long n) { 
     int numSteps = 0; 
     long c = n; 
     while (c != 1) { 
      if (c < CALC_CACHE.length) { 
       int steps = CALC_CACHE[(int) c]; 
       if (steps > 0) { 
        numSteps += steps; 
        break; 
       } 
      } 
      if (c % 2 == 0) { 
       numSteps++; 
       c /= 2; 
      } else { 
       numSteps += 2; 
       if (c > Long.MAX_VALUE/3) 
        throw new IllegalStateException("c is too large " + c); 
       c = (c * 3 + 1)/2; 
      } 
     } 
     if (n < CALC_CACHE.length) { 
      CALC_CACHE[(int) n] = numSteps; 
     } 
     return numSteps; 
    } 

    public static void main(String args[]) { 
     long n = 1, maxN = 0, maxSteps = 0; 
     long startTime = System.currentTimeMillis(); 
     while (System.currentTimeMillis() < startTime + 60000) { 
      for (int i = 0; i < 10; i++) { 
       int steps = calculate(n); 
       if (steps > maxSteps) { 
        maxSteps = steps; 
        maxN = n; 
       } 
       n++; 
      } 
      if (n % 10000000 == 1) 
       System.out.printf("%,d%n", n); 
     } 
     System.out.printf("The highest number was: %,d, maxSteps: %,d for: %,d%n", n, maxSteps, maxN); 
    } 
} 

인쇄

The highest number was: 1,672,915,631, maxSteps: 1,000 for: 1,412,987,847 

은 다중 스레드를 사용합니다. 이 경우 기억을 가진 재귀 사용은 구현하기가 더 쉬웠습니다.

import java.util.stream.LongStream; 

public class Collatz { 
    static final short[] CALC_CACHE = new short[Integer.MAX_VALUE-8]; 

    public static int calculate(long c) { 
     if (c == 1) { 
      return 0; 
     } 
     int steps; 
     if (c < CALC_CACHE.length) { 
      steps = CALC_CACHE[(int) c]; 
      if (steps > 0) 
       return steps; 
     } 
     if (c % 2 == 0) { 
      steps = calculate(c/2) + 1; 
     } else { 
      steps = calculate((c * 3 + 1)/2) + 2; 
     } 
     if (c < CALC_CACHE.length) { 
      if (steps > Short.MAX_VALUE) 
       throw new AssertionError(); 
      CALC_CACHE[(int) c] = (short) steps; 
     } 
     return steps; 
    } 

    static int calculate2(long n) { 
     int numSteps = 0; 
     long c = n; 
     while (c != 1) { 
      if (c < CALC_CACHE.length) { 
       int steps = CALC_CACHE[(int) c]; 
       if (steps > 0) { 
        numSteps += steps; 
        break; 
       } 
      } 
      if (c % 2 == 0) { 
       numSteps++; 
       c /= 2; 
      } else { 
       numSteps += 2; 
       if (c > Long.MAX_VALUE/3) 
        throw new IllegalStateException("c is too large " + c); 
       c = (c * 3 + 1)/2; 
      } 
     } 
     if (n < CALC_CACHE.length) { 
      CALC_CACHE[(int) n] = (short) numSteps; 
     } 
     return numSteps; 
    } 

    public static void main(String args[]) { 
     long maxN = 0, maxSteps = 0; 
     long startTime = System.currentTimeMillis(); 
     long[] res = LongStream.range(1, 6_000_000_000L).parallel().collect(
       () -> new long[2], 
       (long[] arr, long n) -> { 
        int steps = calculate(n); 
        if (steps > arr[0]) { 
         arr[0] = steps; 
         arr[1] = n; 
        } 
       }, 
       (a, b) -> { 
        if (a[0] < b[0]) { 
         a[0] = b[0]; 
         a[1] = b[1]; 
        } 
       }); 
     maxN = res[1]; 
     maxSteps = res[0]; 
     long time = System.currentTimeMillis() - startTime; 
     System.out.printf("After %.3f seconds, maxSteps: %,d for: %,d%n", time/1e3, maxSteps, maxN); 
    } 
} 

인쇄

After 52.461 seconds, maxSteps: 1,131 for: 4,890,328,815 

참고 : 나는

 steps = calculate((c * 3 + 1)) + 1; 

에 두 번째 계산 호출을 변경하는 경우가

After 63.065 seconds, maxSteps: 1,131 for: 4,890,328,815