글 읽기 - 이 두 소스가 어떻게 다른가요??

dbtmddus112 7년 전 0

예전에 풀어서 맞췄던 문제였는데, 최근 다시 돌려보니 계속 시간초과가 뜨길래

잘하는 분들은 어떻게 풀었나 하고 숏코딩 1위에 있는 분 소스를 보고

소스를 수정해봤습니다.

제가 본 소스는 c++ 소스이고 (cubalys 님 작성 소스),

제가 짠 소스는 java소스인데, 아무리 똑같이 구현을 해봐도 수행시간이 10배 이상 차이가 나네요

아래 두 소스가 어떻게 다르길래 수행시간이 10배 이상 나는건가요??

자바가 c++보다 느리다고 해도 이정도 차이가 나나요??

아니면 제가 잘못 구현한 부분이 있나요??

#include <cstdio>
 
int MAP[1001][1001], N, M, T;
 
int MIN(int a, int b) {
    return a > b ? b : a;
}
 
int DFS(int Current, int Parent) {
    int sum = 0;
    for (int i = 1; i <= N; i++) 
        if (MAP[Current][i] && i != Parent)
            sum += DFS(i, Current);
    if (sum == 0) return MAP[Current][Parent];
    return MIN(sum, MAP[Current][Parent]);
}
 
int main() {
    scanf("%d", &T);
    while(T--){
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j < 1001; j++)
                MAP[i][j] = 0;
        scanf("%d%d", &N, &M);
        for (int i = 0; i < M; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            MAP[x][y] = MAP[y][x] = z;
        }
        if (M == 0) printf("0\n");
        else {
            MAP[1][0] = 2147483647;
            printf("%d\n", DFS(1, 0));
        }
    }
}


/////////////////////////////////////////////////////////////////////////
//아래는 제가 짠 자바 소스

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] distance = new int[1001][1001];
	static int n_island;
	
	public static void main(String[] args) {
		Scanner in = new Scanner (System.in);
		int total_cycle = in.nextInt();
		for (int cycle =0; cycle<total_cycle; cycle++){
			for (int i=0; i<1001; i++){
				Arrays.fill(distance[i], 0);
			}
			n_island = in.nextInt();
			int n_river = in.nextInt();
			for (int i=0; i<n_river; i++ ){
				int is1 = in.nextInt();
				int is2 = in.nextInt();
				distance[is1][is2] = in.nextInt();
				distance[is2][is1] = distance[is1][is2];
			}
			
			distance[1][0] = 20*1000 + 2000000;
			int result = recursive_search(1,0);
			if (result == 20*1000 + 2000000){
				result =0;
			}
			System.out.println(result);
		}
	}//end main
	
	static int recursive_search(int current, int parent){
		int sum=0;
		for(int i=1; i<=n_island;i++){
			if (distance[current][i]>=1 && i!=parent){
				sum = sum + recursive_search( i,current);
			}
		}
		if(sum==0){
			return distance[current][parent];
		}
		return MIN(sum, distance[current][parent]);		
	}

	static int MIN(int a, int b) {
		return a > b ? b : a;
	}
 
}

KimJJ 7년 전 0

뭐 코드를 자세히 들여다보진 않았지만, C++과 JAVA라면 그 정도 차이는 날 수 있습니다.

일단 JAVA에서는 배열형이 연속된 메모리에 배치된다는 Guarantee가 없습니다. 이 말은 캐시 메모리의 효과를 기대할 수 없다는 것이죠.

그리고 자바의 JIT 컴파일러가 프로파일링을 바탕으로 최적화된 코드를 생성하기 위해서는 꽤 많은 반복수행을 필요로 합니다. 수행시간이 짧을 수밖에 없는 경시 환경에서는 제대로 동작할래야 할 수가 없지요.

사실상 인터프리터 모드로 돌아야 하므로 10배밖에 차이가 안 나면 오히려 JAVA가 상당히 빠른 것임을 알 수 있는거죠.

dbtmddus112 7년 전 0

답변 감사합니다!

꽤 많은 반복 수행이라는게 반복문 등으로 상당히 여러차례 돌아간 후부터 빨라진다는 건가요??

그러면 반복수행횟수가 상당히 큰 반복문 내에서는 자바가 그렇게까지 느리지는 않지만,

dinamic 프로그래밍 적용이 어려운 상황에서 여러차례의 재귀함수 호출에서는 자바가 느려지는건가요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 두 소스가 어떻게 다른가요??

dbtmddus112 7년 전 0

KimJJ 7년 전 0

dbtmddus112 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말