ARCTIC (남극기지) 소스코드 성능 문의 드립니다.

  • gloryof11
    gloryof11

    ARCTIC

    안녕하세요 한창 배워가는 개발자입니다.
    위 문제는 '정답' 을 받기는 했지만, 성능상 이해가 되지 않는 부분이 있어 이렇게 문의를 드리게 되었습니다.
    고수님들의 고견 부탁드립니다.

    <궁금한점>
    메모이제이션으로 최대 97% 정도 sqrt() 연산을 줄였음에도 수행시간은 미묘하게 더 걸리는 것 같습니다. 어떤 이유 때문일까요? (참고로, 제가 LOCAL 에서 테스트 했을때는 2배 가량 수행속도가 빨랐습니다.)

    <비교가 필요한 함수>

    • getDistance1() : 그냥 코드
    • getDistance() : 메모이제이션 고려한 코드

    /*
    1) A = {본부}
    2) A 집합의 각 원소와 가장 근접한 기지 탐색
    3) 탐색된 기지를 A에 추가
    4) 추가할때 A 집합에 속한 기지와 탐색된 기지의 거리를 구하여, 최대가 되는 값이 정답임
    5) 2,3 반복
    6) memoization 으로 거리 계산 중복 연산 제거
    */
    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    unsigned long called;
    
    int TC;
    int posN;
    float pos[100][3];
    int setN;
    float set[100][2];
    float setmemo[100][100];
    float answer;
    float dist;
    float jmin, kmin;
    int jidx, kidx;
    
    int insertSet(int idx)
    {
        set[setN][0] = pos[idx][0];
        set[setN][1] = pos[idx][1];
        pos[idx][2] = 1;
        return ++setN;
    }
    
    float getDistance1(float x1, float y1, float x2, float y2)
    {
        called++;
    
        return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
    }
    float getDistance(int j, int k)
    {
        if(setmemo[j][k] != 0) {
            return setmemo[j][k];
        }
        else {
            called++;
    
            setmemo[j][k] = sqrt((set[j][0] - pos[k][0])*(set[j][0] - pos[k][0]) + (set[j][1] - pos[k][1])*(set[j][1] - pos[k][1]));        
        }
        return setmemo[j][k];
    }
    int main(void)
    {
        clock_t start= clock();
        freopen("input.txt", "r", stdin);
        setbuf(stdout, NULL);
    
        scanf("%d", &TC);
        for(int i=0;i<TC;i++)
        {
            // input
            scanf("%d", &posN);
            for(int j=0;j<posN;j++)
            {
                scanf("%f %f",&pos[j][0], &pos[j][1]);
                pos[j][2] = 0;
            }
    
            // init
            answer = 0;
            setN = 0;
            for(int j=0;j<posN;j++)
                for(int k=0;k<posN;k++)
                    setmemo[j][k] = 0;
    
            // code
            insertSet(0);   // 본부를 집합에 포함시킨다.
    
            while(setN<posN)
            {
                jmin = 2000;
                kmin = 2000;
                for(int j=0;j<setN;j++)
                {
                    for(int k=0;k<posN;k++)
                    {
                        if(pos[k][2] == 1) continue;    // 이미 set 에 포함되었으면 continue
    
                        //dist = getDistance1(set[j][0], set[j][1], pos[k][0], pos[k][1]);
                        dist = getDistance(j,k);    // memoization
    
                        if(kmin > dist) {
                            kmin = dist;
                            kidx = k;
                        }
                    }
    
                    if(jmin > kmin) {
                        jmin = kmin;
                        jidx = kidx;
                    }
                }
    
                insertSet(jidx);    // 선택된 집합과 가장 거리가 가까운 기지를 포함시킨다.
    
                if(answer < jmin) answer = jmin;
            }
    
            // output
            printf("%.2f\n", answer);
        }
    
        printf("\ntime : %d %ld\n",clock()-start,called);
    
        return 0;
    }
    


    10년 전
3개의 댓글이 있습니다.
  • Being
    Being

    최적화 관련한 건 컴파일된 결과물을 열어보는 것이 가장 확실한데요, 그냥 추측하기에는 getDistance1()은 인라이닝되고 getDistance()는 인라이닝되지 않은게 아닌가 싶습니다.


    10년 전 link
  • Being
    Being

    혹시 로컬 환경에서 테스트하실 때 컴파일러 최적화 옵션을 켜셨는지요?


    10년 전 link
  • gloryof11
    gloryof11

    툴사용에 익숙치 않아 옵션으로 확인은 못했습니다.
    하지만, getDistance1() 의 코드를 main 함수에 구현하니 수행 속도가 빨라졌습니다.
    추측하신것이 원인이 맞는것 같습니다!
    Being님 감사합니다!!


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.