java에서 continue와 조건 단순화가 필요한 이유

Yellta·2024년 6월 8일

아래 두 코드의 차이점은 무엇일까? 어떤 점이 다르길래 수행 속도에서 차이가 나는 것일까?
위의 코드는 7ms이고 아래의 코드는 6ms의 결과를 가져다 준다. 연산의 횟수가 똑같은 것 같은데 사유가 뭔지 그 이유를 알아보자!

// 첫 번째
        for (int i=0;i< arr.length;i++){
            int maxVal=0;
            for (int j=1;j<=k&&i-j+1>=0;j++){
                maxVal=Math.max(maxVal,arr[i-j+1]);
                if (i-j+1==0) dp[i]=Math.max(dp[i],maxVal*j);
                else dp[i]=Math.max(dp[i],dp[i-j]+maxVal*j);
            }
        }
// 두 번째
        for (int i=0;i< arr.length;i++){
            int maxVal=0;
            for (int j=1;j<=k;j++){
                if (i-j+1<0) continue;
                maxVal=Math.max(maxVal,arr[i-j+1]);
                if (i-j+1==0) {dp[i]=Math.max(dp[i],maxVal*j);continue;}
                dp[i]=Math.max(dp[i],dp[i-j]+maxVal*j);
            }
        }

두 번째 코드가 실행이 더 빠른 이유

두 개의 코드는 같아보이지만 결정적으로 다른 부분이 있다.

  for (int j=1;j<=k&&i-j+1>=0;j++){
                maxVal=Math.max(maxVal,arr[i-j+1]);

for (int j=1;j<=k;j++){
                if (i-j+1<0) continue;
                maxVal=Math.max(maxVal,arr[i-j+1]);

해당부분이다.

두 개의 코드는 동일한 연산을 수행하지만 차이점이 있다. 아래의 코드가 왜 더 빠른지 이해하려면 약간의 배경지식이 필요하다.

java와 JVM의 특성은 꼭 알아두는 것이 좋다.

Java의 compile과정 이해하기

java는 OS에 종속적인 언어가 아니고 JVM에 종속적인 언어이다. java가 JVM을 사용하기 때문에 발생하는 특징들이 있다.

1. OS종속언어보다 느리다.

코딭테스트를 볼 때 C++을 추천하는 이유이다. C++은 OS에 종속적인 언어이지만 java처럼 중간에 JVM을 거치지않고 OS에서 컴파일되어 바로 수행된다. 이는 수행속도가 java보다 빠르다는 것을 의미한다.

때문에 코딩테스트에서 C++을 추천하는 이유이다. 백준같은 곳을 둘러보면 java, python에게 시간을 조금 더 주는경우가 꽤나 있다. 이는 JVM을 거치기 떄문에 속도가 느린 자바의 특성을 감안한 이유이기도 하다.

해당 단점을 보완하기 위한 방식

자바는 바이트코드(컴파일된 자바 코드)를 하드웨어의 기계어로 변환해주는 JIT컴파일러를 사용한다. 이를 통해 속도의 격차를 줄이고 있다.

📢 JVM을 사용하는 java언어의 장점

JVM을 사용하기 떄문에 느리지만 반대로 JVM을 사용하기 때문에 OS에 종속적이지 않다는 특징이 있다. 이는 JVM만 있으면 어느 OS던 구애받지않고 java언어를 사용할 수 있다는 의미이다.

java는 JVM와 JIT컴파일러를 사용한다. 근데 그래서?

JIT(Just-In-Time) 컴파일러는 다양한 최적화 기술들을 제공한다. bytecode를 native Machine code로 변환하고 더 효율적이고 빠르게 실행될 수 있도록 한다.

루프 조건 평가 최적화

1. loop Unrolling(루프 언롤링)

루프의 반복 횟수를 줄이기 위해 한 번의 반복에서 여러 번의 루프 본문을 실행하는 방법

// 원래의 루프
for (int i = 0; i < 10; i++) {
    process(i);
}

// 루프 언롤링 후
for (int i = 0; i < 10; i += 2) {
    process(i);
    process(i + 1);
}

2. Inlining(인롤링)

함수 호출을 method Body에서 수행하는 방법. 메소드 오버헤드를 줄일 수 있다.

//Inlining 전
public int add(int a, int b) {
    return a + b;
}

public void main() {
    int sum = add(5, 3);
}
//--------------------------------------------

// Inlining 후
public void main() {
    int sum = 5 + 3;
}

메소드 오버헤드?
프로그램에서 메소드를 호출할 때 발생하는 추가적인 처리 시간과 자원 소비를 의미한다.
c++에서도 main에서 수행하는 것과 함수를 호출해서 수행하는 것의 처리 시간에서 차이가 난다. java도 마찬가지이다.

3. Loop-Invariant Code Motion(루프 인변수 코드 이동)

루프 내부에서 반복마다 동일한 결과를 생성하는 계산을 루프 외부로 빼내는 방법

// 원래의 루프
for (int i = 0; i < n; i++) {
    int result = constantFunction();
    process(result, i);
}

// 루프 인변수 코드 이동 후
int result = constantFunction();
for (int i = 0; i < n; i++) {
    process(result, i);
}

4. Short-Circuit Evaluation(조건문 단락 평가)

논리 연산자 && 혹은 ||를 사용하여 첫 번째 조건이 결과를 결정할 수 있다. 첫 번째 조건이 false면 두 번째 조건은 수행되지 않는다.

if (conditionA && conditionB) {
    // conditionA가 false이면 conditionB는 평가되지 않습니다.
}

5. 루프 조건 평가 단순화

루프 조건을 단수화하고 조건문을 내부로 옮기면 컴파일러가 루프를 좀 더 효율적으로 최적화할 수 있다. 단순화된 루프 조건은 컴파일러가 루프의 종료 조건을 빠르게 결정하도록 한다.

// 복잡한 조건의 루프
for (int i = 0; i < n && someComplexCondition(i); i++) {
    process(i);
}
//두 가지의 조건을 동시에 평가한다. 물론 조건문 단락평가에 의해서 첫 번쨰 조건이
//false이면 뒤의 연산은 수행하지 않는다.

//===================================
// 조건을 내부로 옮긴 루프
for (int i = 0; i < n; i++) {
    if (!someComplexCondition(i)) break;
    process(i);
}

결론

// 첫 번째
        for (int i=0;i< arr.length;i++){
            int maxVal=0;
            for (int j=1;j<=k&&i-j+1>=0;j++){
                maxVal=Math.max(maxVal,arr[i-j+1]);
                if (i-j+1==0) dp[i]=Math.max(dp[i],maxVal*j);
                else dp[i]=Math.max(dp[i],dp[i-j]+maxVal*j);
            }
        }
// 두 번째
        for (int i=0;i< arr.length;i++){
            int maxVal=0;
            for (int j=1;j<=k;j++){
                if (i-j+1<0) continue;
                maxVal=Math.max(maxVal,arr[i-j+1]);
                if (i-j+1==0) {dp[i]=Math.max(dp[i],maxVal*j);continue;}
                dp[i]=Math.max(dp[i],dp[i-j]+maxVal*j);
            }
        }