이 프로그램의 실행 시간을 어떻게 단축시킬 수 있습니까?

Question

InterviewStreet에서 연습 프로그램을 작성 중이며 Java 솔루션에 허용되는 최대 시간은 5 초이지만 5.15xx 초로 실행되는 솔루션이 있습니다. 5 초 안에 얻을 수있는 것이 내가 할 수있는 일이 있습니까? 또한 256MB의 한계가있어서 문제의 가장 많은 시간과 메모리 효율적인 해결책이라고 할 수 있습니다.

편집 : N 및 K에 가능한 값은 N < = 10^9 및 K < = N 이니 BigInteger를 사용하여 모든 작업을 수행했습니다. 최대 재판 횟수는 10000입니다. 따라서 기본적으로 재판 횟수를 입력 한 다음 각 재판 횟수에 대한 정수 값 쌍을 입력하고 프로그램에서 두 번째 루프의 방정식에 대한 이항 계수의 세 가지 버전을 계산합니다. 배열로 모든 것을 읽은 다음 배열을 처리하고 세 번째 배열로 결과를 저장하는 것이 더 빠를 것이라고 생각했기 때문에 세 번째 루프에서 처리하는 것이 더 빠를 것이라고 생각했기 때문입니다. 같은 루프에서 모든 것을 시도했는데 느리게 실행되었습니다.

저는 이항 계수 (nCr - 또는 n은 r을 선택하십시오. 모두 똑같은 것을 말하기위한 다른 방법입니다)를 계산하기 위해 3 개 또는 4 개의 알고리즘을 시도했습니다. 알고리즘 중 일부는 c [n] [k]와 같은 2 차원 배열을 포함합니다. 이것은 제가 제출 한 유일한 해결책으로, 일종의 메모리 오류로 돌아 가지 않았습니다. 대답은 mod (10^6) + 3으로 출력되어야합니다. 왜냐하면 nCr * nCr의 응답이 상당히 커지기 때문입니다. 프로그램의 샘플 실행은 다음과 같습니다

3 

4 1 
5 2 
90 13 

2 
5 
815483 

가 계산하는 자신의 컴퓨터에 전달해야하기 때문에 기본적으로, 나는 코드를 입력하고 그들의 테스트 케이스에 대해 실행, 빠른 머신에서 실행 할 수 없습니다 및 나는 그들의 테스트 케이스가 무엇인지 알지 못한다. 단지 입력이 위에 주어진 범위 내에 있다는 것이다.

그리고 프로그램 자체 :

import java.math.BigInteger; 
import java.util.Scanner; 

public class Solution { 

public BigInteger nCr(int n, int r) { 
    if (r > n) { 
     return BigInteger.ZERO; 
    } 

    if (r > n/2) { 
     r = n - r; 
    } 
    BigInteger result = BigInteger.ONE; 

    for (int i = 0; i < r; i++) { 
     result = result.multiply(BigInteger.valueOf(n - i)); 
     result = result.divide(BigInteger.valueOf(i + 1)); 
    } 
    return result; 
} 

public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    BigInteger m = BigInteger.valueOf(1000003); 
    Solution p = new Solution(); 
    short T = input.nextShort(); // Number of trials 
    BigInteger intermediate = BigInteger.ONE; 
    int[] r = new int[T]; 
    int[] N = new int[T]; 
    int[] K = new int[T]; 

    short x = 0; 

    while (x < T) { 
    N[x] = input.nextInt(); 
    K[x] = input.nextInt(); 
    x++; 
    } 

    x = 0; 
    while (x < T) { 
    if (N[x] >= 3) { 
      r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue(); 
     } else { 
      r[x] = 0; 
    } 
    x++; 
    } 

    x = 0; 
    while (x < T) { 
    System.out.println(r[x]); 
    x++; 
    } 
} 

}

Answer 1

하지 전적으로 알고리즘을 달성하기 위해 노력하지만 게시물의 당신의 태그를 기반으로 이항 계수 뭔가를 추측하고있어 무엇인지.

당신은 내 제안 결과를 수정하는 경우 확인해야하지만, 당신이 당신의 동안 두 가지를 병합 할 수있는 것 같습니다 루프 :

원본 :

while (x < T) { 
    N[x] = input.nextInt(); 
    K[x] = input.nextInt(); 
    x++; 
} 

x = 0; 
while (x < T) { 
if (N[x] >= 3) { 
     r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue(); 
    } else { 
     r[x] = 0; 
    } 
    x++; 
} 

새로운 기능 :

x = 0; 
while (x < T) { 

//this has been moved from your first while loop 
N[x] = input.nextInt(); 
K[x] = input.nextInt(); 

if (N[x] >= 3) { 
     r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue(); 
    } else { 
     r[x] = 0; 
    } 
    x++; 
} 

Answer 2

profilerm (예 : jvisualvm)을 사용하여 실행하려고 시도하고이 클래스를

-Dcom.sun.management.jmxremote

프로세스에 연결하고 프로필을 시작하십시오.