아규먼트 유무에 따른 연산시간 변화(SWEA_7965)

SWEA의 7965_ 퀴즈 문제

(number)%p 연산을 위해 power에 아규먼트 p를 주도록 하는 경우와 함수 안에서 p를 따로 정의한 후 사용하는 경우 연산 시간에 상당한 차이가 보인다.

DP를 사용하지 않는 경우

이 경우에는 파라미터 p가 있고 없음의 차이가 비교적 작지만, 파라미터가 있는 쪽이 연산시간이 더 큰 걸 확인할 수 있다.

1. 파라미터가 있는 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	int p = 1000000007;
	int T = Integer.parseInt(br.readLine());
	for (int t = 1; t <= T; t++) {
		long sum = 0l;
		int N = Integer.parseInt(br.readLine());
		for (int i = 1; i <= N; i++) {
			sum+= (power(i,i,p)%p);
			sum%=p;
		}
		System.out.println("#"+t+" "+sum%p);
	}
}

private static long power(long num, long expo, int p) {
	if(expo==1) {
		return num%p;
	}
	long temp = power(num, expo/2, p)%p;
	if(expo%2==1) {
		return ((temp*temp%p)*num)%p;
	}
	return temp*temp%p;
}

}

2. 파라미터가 없는 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int p = 1000000007;
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			long sum = 0l;
			int N = Integer.parseInt(br.readLine());
			for (int i = 1; i <= N; i++) {
				sum+= (power(i,i)%p);
				sum%=p;
			}
			System.out.println("#"+t+" "+sum%p);
		}
	}

	private static long power(long num, long expo) {
		int p = 1000000007;
		if(expo==1) {
			return num%p;
		}
		long temp = power(num, expo/2)%p;
		if(expo%2==1) {
			return ((temp*temp%p)*num)%p;
		}
		return temp*temp%p;
	}

}

DP를 사용한 경우

이 경우 반복이 적어 둘 다 Pass 하긴 하지만, 연산 시간에 2배 이상의 차이를 보인다.

1. 파라미터가 있는 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int p = 1000000007;
		int T = Integer.parseInt(br.readLine());
		long[] arr = new long[1000001];
		for (int i = 1; i < 1000001; i++) {
			arr[i] = power(i,i,p);
		}
		for (int t = 1; t <= T; t++) {
			long sum = 0l;
			int N = Integer.parseInt(br.readLine());
			for (int i = 1; i <= N; i++) {
				sum+= arr[i];
				sum%=p;
			}
			System.out.println("#"+t+" "+sum%p);
		}
	}

	private static long power(long num, long expo, int p) {
		if(expo==1) {
			return num%p;
		}
		long temp = power(num, expo/2, p)%p;
		if((expo&1)==1) {
			return ((temp*temp%p)*num)%p;
		}
		return temp*temp%p;
	}

}

2. 파라미터가 없는 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int p = 1000000007;
		int T = Integer.parseInt(br.readLine());
		long[] arr = new long[1000001];
		for (int i = 1; i < 1000001; i++) {
			arr[i] = power(i,i);
		}
		for (int t = 1; t <= T; t++) {
			long sum = 0l;
			int N = Integer.parseInt(br.readLine());
			for (int i = 1; i <= N; i++) {
				sum+= arr[i];
				sum%=p;
			}
			System.out.println("#"+t+" "+sum%p);
		}
	}

	private static long power(long num, long expo) {
		int p = 1000000007;
		if(expo==1) {
			return num%p;
		}
		long temp = power(num, expo/2)%p;
		if((expo&1)==1) {
			return ((temp*temp%p)*num)%p;
		}
		return temp*temp%p;
	}

}

(number)%p 연산을 위해 power에 아규먼트 p를 주도록 하는 경우와 함수 안에서 p를 따로 정의한 후 사용하는 경우 연산 시간에 상당한 차이가 보인다.

 

p를 정의하지 않고 아규먼트로 주는 것이 이렇게 큰 차이를 만든다고? 싶어 SSAFY 교수님께 여쭤보았다.

 

기본시간+개수* 회수 만틈 시간이 더 걸리죠. 잘 찾으셨네요. 회수가 작으면 큰 차이가 없고 static이 지역보다 시간이 더 걸립니다. 지역변수를 사용하는 것이 좋습니다.

 

라는 답변을 받았다.

local 정의 > static > 아규먼트 인 것 같다.