글 읽기 - #define mod 와 int mod의 차이?

dmswl022329 2년 전 0

어떤 부분에서 차이가 나는건지 알 수 있을까요?

아직 제대로 공부를 안했는지 이해가 안가네요 ㅠㅠ

#include<bits/stdc++.h>
#define mod 1000000009 // 얘를 쓰면 통과함
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;


ll a1, b1, c1, d1;
//ll mod = 1000000009; // 얘를 쓰면 시간초과 남

matrix operator * (const matrix &a, const matrix &b){
	ll size = a.size();
	// vector<vector<ll>> 를 size 크기만큼 size 크기의 vector<ll> 로 초기화;
	matrix res(size,vector<ll>(size));
	for(ll i = 0; i < size; i++){
		for(ll j = 0; j < size; j++){
			for(ll k = 0; k < size; k++){
					res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
			}
		}
	}
	return res;
}


// 행렬 a의 n 제곱
matrix power(matrix a, ll n){
	ll size = a.size();
	matrix res = matrix(size, vector<ll>(size));
	for(ll i = 0; i < size; i++) res[i][i] = 1;
	while(n > 0){
		if(n % 2 == 1) res = res * a;
		n /= 2;
		a = a * a;
	}
	return res;
}

void printmatrix(const matrix &a){
	ll size = a.size();
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}

ll mul(ll A, ll B){
	if(B == 1) return A;
	if(B % 2 == 0) return mul((A * 2) % mod, (B / 2)) % mod;
	else return (mul(A, B - 1) + A) % mod;
}

void initA(matrix &a){
	ll size = a.size();
	for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            if(i <= j) a[i][j] = 1;
        }
    }
    a[size - 1][size - 2] = 1;
    a[size - 1][size - 1] = 0;
}

ll sol(matrix &a){
	ll res = 0;
	ll size = a.size();
	for(int i = 0; i < size - 1; i++) res = (res + mul(a[0][i], a1) + mod) % mod;
	res = (res + mul(a[0][size - 1], b1) - mul(a[0][size - 1], a1) + mod) % mod;
	return res;
}

int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	int T;
	cin >> T;
	while(T--){
		cin >> a1 >> b1 >> c1 >> d1;
		matrix A(c1 + 2, vector<ll>(c1 + 2));
		initA(A);
		A = power(A, d1 - 1);
		cout << sol(A) << "\n";
	}
    
	return 0;
}

Green55 2년 전 1

mod가 상수인 경우 컴파일러가 최적화를 해줄 수 있어서 유의미하게 시간차이가 납니다.

따라서 const ll mod = 1000000009; 로 해주시면 비슷하게 시간이 나오실겁니다.

dmswl022329 2년 전 0

ll mod = 1000000009 로 선언하게 되면

연산할때마다 mod 를 찾아서 값을 가져오기때문에 시간이 오래걸리는건가요?

컴파일러가 최적화를 해줄 수 있다는말은 와닿긴 하지만 어떤 과정을 통해 최적화를 해주는건지 모르겠네요

Green55 2년 전 0

모듈러 자체가 원래 꽤 오래 걸리는 비싼 연산인데, 상수에 대한 모듈러는 아예 어셈블리단에서 더 효율적인 알고리즘을 사용하는 것으로 알고 있습니다.

저도 자세히는 모르는 내용이고 꽤 이론적으로 깊은 공부가 필요할거 같습니다.

dmswl022329 2년 전 0

모듈러 연산이 오래걸리는건 처음 알았네요

좋은 정보 감사합니다!

공부가 필요함을 느꼈네요

혹시 시간 괜찮으시면 13246번의 질문에 대답해주실 수 있나요?

바쁘시면 그냥 지나가셔도 됩니다.

https://www.acmicpc.net/board/...

hojoon0205 2년 전 5

컴파일러는 상수가 적혀있으면 생각보다 많은 부분에서 최적화를 합니다.

매우 단순한 예시로 a *= 48; 이라는 간단한 코드를 어셈블리로 직역한다면

// eax 레지스터에 a값이 저장되어 있음 
imul 48, eax // eax = eax * 48

이 한 줄 만으로도 끝낼 수 있지만 실제로는 다음과 같이 최적화를 합니다.

// eax 레지스터에 a값이 저장되어 있음 
lea (eax, eax, 2), eax // eax = eax + eax*2 
sal 4, eax // eax <<= 4

위 어셈블리 코드에 대해서 좀 더 구체적인 설명을 해보자면

imul x, y  :  y = x * y 역할을 하는 단순한 명령어입니다. 
lea x, y : y = &x 라고 생각하시면 됩니다. x의 주소값을 y에 저장합니다.
(i, b, s) : b+s*i를 주소값으로 취급하겠다는 의미입니다. 
            int arr[10]; 와 같이 arr이 정의되었을 때 b의 자리에는 arr[0]의 주소값이 들어가고, s의 자리에는 int의 바이트 수인 4가 들어가 (i, arr, 4)같이 표현되며, 
            이는 arr[i]를 의미합니다. 위의 예시에서는 배열 주소값 빠르게 계산하라고 만들어놓은 걸 *3을 빠르게 하는데 사용하고 있는 것입니다.
sal x, y : y <<= x 라고 생각하시면 됩니다. 위의 예시에서는 *16을 하는데 쓰였습니다.

이렇게 컴파일러는 상수와 관련되어 있으면 단순한 연산조차 위와 같이 최적화를 해버립니다. mod연산의 경우 나눗셈이 오래 걸리는 연산이라 덩달아 오래 걸리게 되는 것인데(어셈블리 상에서 나눗셈을 하면 몫과 나머지가 같이 계산됩니다) 상수로 쓰여 있으면 상수에 맞춰서 어셈블리 연산이 아예 바뀌어 버립니다.

ckdgus2482 2년 전 2

디스어셈블 해보면 어떤 차이인지 알 수 있습니다.

우선 #define은 전처리 명령어로 컴파일 이전에 코드 자체가 치환되는 것이기 때문에, 기계어 상에서도 리터럴이 그대로 들어갑니다.

테스트해보니 constexpr이나 const로 해도 마찬가지로 리터럴이 그대로 들어가더군요.

반면 const가 아닌 전역변수인 경우는 오퍼랜드가 변수 주소에 대한 참조로 들어갑니다.

그런데 그것만으로 극명한 시간차이가 날 것 같지는 않고, 다른 차이의 가능성을 생각해보면 캐시 히트율에 차이가 있을지도 모르겠네요.

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

문제

문제

출처

ICPC

#define mod 와 int mod의 차이?

dmswl022329 2년 전 0

Green55 2년 전 1

dmswl022329 2년 전 0

Green55 2년 전 0

dmswl022329 2년 전 0

hojoon0205 2년 전 5

ckdgus2482 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말