알고리즘 문제풀이 사이트에서 자바로 풀때 속도 올리는 방법

atcoder.jp 에서 'B - Frog 2' 문제를 자바로 풀어 보다가,
'왜 내 코드는 다른 사람들 보다 느릴까?' 고민한 끝에...

간단한 문제이기는 하지만, 드디어 속도로 4등했습니다. ^^

처음에는 489ms 부터 시작했습니다. 마지막에는 118ms까지 줄였네요

그래서 이번에는 속도를 개선하는 방법에 대해서 이야기 해보려고 합니다.
처음 코드와 마지막 최적화 된 코드를 비교해 보실 분은 아래 링크를 참고하세요.
처음 Accept된 코드 489ms : https://atcoder.jp/contests/dp/submissions/9143731
최종 Accpet된 코드 118ms : https://atcoder.jp/contests/dp/submissions/9143913

Scanner는 느리다, 반드시 다른거 써야 한다.

489ms 에서 133ms 까지 대략 350ms 정도 확 준게 보이실 겁니다.
보통은 아래 처럼, Scanner를 사용해서, 입력을 받게 됩니다.

Scanner sc = new Scanner(System.in);

테스트 케이스가 돌 때는, 많은 수의 숫자를 Scanner를 통해서 입력 받게 되는대, Scanner때문에 많이 느립니다.
이래서, topcoder에서는 문제 풀때, method를 주고 실행하게 하는 구나! 깨달았습니다.
Scanner의 느린 속도와, 이를 개선하는 방법은 아래 링크 참고하세요.

• Fast I/O in Java in Competitive Programming
• https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

static 변수가 약간 더 빠르다

이제 부터는 몇백ms 정도 까지는 아니구요, 10ms 미만의 약간씩 개선되는 것입니다.
'B - Frog 2'문제 에서는 각 돌로 이동할 때, 각 돌의 이동 비용을 배열로 입력 받아야 하는대,
이 때 #1 처름 일반 변수로 하는 것 보다, #2 처럼 static으로 하는 것이 약간 더 빠릅니다.

#1 non static 변수로 선언

int[] h = new int[N];

for(int i=0; i<N; ++i)
    h[i] = sc.nextInt();

#2 static 변수로 선언

Main 클래스의 멤버변수로 h를 선언하고, 메서드 안에서 h 에 new int[N] 해서 사용하는 것이 약간 빠릅니다.
하지만, 이부분은 옵티마이저에서 어떻게 타느냐에 따라서, 더 느릴 수 도 있습니다.

static int[] h

h = new int[N];

for(int i=0; i<N; ++i)
    h[i] = sc.nextInt();

1번의 비교도 아껴야 한다.

아래와 같이 t 값을 최대값으로 해두고서, Math.min에서 가장 작은 값을 찾는 것은 약간느린 코드입니다.

        for(int j=1; j<N; ++j) {
            int t = Integer.MAX_VALUE;
            boolean bContinue = true;
            for(int d=1; d<=K && bContinue; ++d) {
                int i = j-d;
                if(i>=0){
                    t = Math.min(Math.abs(h[i]-h[j]) + v[i], t);
                }
                else {
                    bContinue = false;
                }
            }

            v[j] = t;
        }

문제 정의에 따라서, N은 최소 2부터 시작 하고, h = new int[N] 이기 때문에, h[1-1] - h[1] 는 항상 존재 합니다. 따라서 아래와 같이 코딩하는게 가능하고, 약간 더 빠르게 동작합니다. 일종의 루프 언롤링이라고 볼 수 도 있습니다.

        for(int j=1; j<N; ++j) {
            int t = Math.abs(h[j-1]-h[j]) + v[j-1];
            boolean bContinue = true;
            for(int d=2; d<=K && bContinue; ++d) {
                int i = j-d;
                if(i>=0){
                    t = Math.min(Math.abs(h[i]-h[j]) + v[i], t);
                }
                else {
                    bContinue = false;
                }
            }

            v[j] = t;
        }

중간에 loop를 나와야 할 때, 어떻게 코딩하는게 빠를까?

bContinue를 사용해서, loop를 나와야할 조건을 만들었는대, 이렇게 하는 것 보다 j-d를 직접 루프의 조건에 넣는 것이 좀더 빠릅니다.

        for(int j=1; j<N; ++j) {
            int t = Math.abs(h[j-1]-h[j]) + v[j-1];
            boolean bContinue = true;
            for(int d=2; d<=K && bContinue; ++d) {
                int i = j-d;
                if(i>=0){
                    t = Math.min(Math.abs(h[i]-h[j]) + v[i], t);
                }
                else {
                    bContinue = false;
                }
            }

            v[j] = t;
        }

(j-d)>=0 조건을 직접 루프에 넣어 줍니다.

        for(int j=1; j<N; ++j) {
            int t = Math.abs(h[j-1]-h[j]) + v[j-1];
            for(int d=2; (d<=K) && (j-d>=0); ++d) {
                t = Math.min(Math.abs(h[j-d]-h[j]) + v[j-d], t);
            }
            v[j] = t;
        }

알고리즘 문제풀어 보면서, 그래도 한번은 내 코드가 순위 안에 들어가기를 바랬는대... T^T 소원 풀었습니다.