글 읽기 - 나눗셈을 너무 많이 하지 맙시다.

jh05013 4년 전 5

의문의 TLE를 받으면서 게시판에 질문을 올리기 직전까지 갔다가, 스스로 원인을 발견했습니다.

위의 코드에서 matmul을 호출할 때마다 C.A[i][j]+= A.A[i][k]*B.A[k][j] % mod; 을 약 466만 번 실행하게 되는데, 문제는 이때 사용되는 idiv 연산이 매우 느리다는 것입니다. 그리고 이 matmul 자체도 30번 호출하기 때문에 이 함수 안에서 약 1억 4000만 번의 idiv가 발생하게 됩니다. 실제로 ideone에서 돌려 봤을 때 1.8초 정도 걸렸습니다.

밑의 코드처럼 const ll MOD로 나누거나, % mod 자체를 % 1000000009로 바꾸면, 컴파일러가 최적화를 하면서 idiv 연산을 쓰지 않게 되고, 500 ms 이내로 AC를 받습니다.

언급할 가치가 있는 함정(?)이라고 생각하여 남겨 봤습니다.

// TLE
Matrix matmul(Matrix &A, Matrix &B, ll mod){
    int N = A.n, M = B.n, K = B.m;
    Matrix C(N, K);
    for(int i=0; i<N; i++) for(int j=0; j<K; j++){
        for(int k=0; k<M; k++) C.A[i][j]+= A.A[i][k]*B.A[k][j] % mod;
        C.A[i][j]%= mod;
    }
    return C;
}

// AC
const ll MOD = 1000000009;
Matrix matmul(Matrix &A, Matrix &B){
    int N = A.n, M = B.n, K = B.m;
    Matrix C(N, K);
    for(int i=0; i<N; i++) for(int j=0; j<K; j++){
        for(int k=0; k<M; k++) C.A[i][j]+= A.A[i][k]*B.A[k][j] % MOD;
        C.A[i][j]%= MOD;
    }
    return C;
}

kipa00 4년 전 3

언급하신 부분 이외에도 최적화가 일어날 여지가 있는 부분이 있어 댓글을 남깁니다.

Matrix가 단순히 2차원 배열이라면, 아래와 같이 구현할 경우 cache hit rate가 유의미하게 증가하면서 시간의 이득을 볼 수 있습니다.

for (int i=0; i<N; i++) {
    for (int j=0; j<M; j++) {
        for (int k=0; k<K; k++) {
            C.A[i][k] += A.A[i][j] * B.A[j][k] % MOD;
        }
    }
}
for (int i=0; i<N; i++) {
    for (int j=0; j<K; j++) {
        C.A[i][j] %= MOD;
    }
}

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

문제

문제

출처

ICPC

나눗셈을 너무 많이 하지 맙시다.

jh05013 4년 전 5

kipa00 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말