SORTGAME 질문입니다~!

  • Signin
    Signin

    안녕하세요~
    문제 SORTGAME 을 풀다가,
    질문이 있어서 올리게 되었습니다.

    JMBOOK의 모범 코드를 가지고 테스트를 해 봤는데요,
    저의 컴퓨터에서는 실행시간이 8초를 훨씬 웃도는데
    Online Judge에서는 이렇게 간단히 500ms만에 답이 나오는게
    신기해서 여쭈어보게 되었습니다.

    저의 노트북 성능이 안 좋은 것인가요~?
    (CPU는 2117u, 램은 4GB 입니다.ㅠㅠ)
    아니면 뭔가 운영체제나 컴파일러에 따른 속도 차이가 나는 것인가요~?

    소스코드는 다음과 같습니다.(책과 90% 똑같습니다.)

    #include <iostream>
    #include <vector>
    #include <map>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    
    map<vector<int>, int> dist;
    
    
    void printVector(vector<int> &v)
    {
        int i=0; 
    
        for(i=0; i<v.size(); i++)
            cout << v[i] << " ";
        cout << endl;
    }
    
    
    
    void precalc(int n)
    {
        vector<int> start(n);
        for(int i=0; i<n; i++)  start[i] = i;
    
        queue< vector<int> > q;
        q.push(start);
        dist[start] = 0;
    
        while(!q.empty())
        {
            vector<int> here = q.front();
            q.pop();
    
            int cost = dist[here];
    
            for(int i = 0; i < n; i++)
            {
                for(int j = i+2; j <= n; j++)
                {
                    reverse(here.begin() + i, here.begin() + j);
    
                    if(dist.count(here) == 0)
                    {
                        dist[here] = cost + 1;
                        q.push(here);
                        //cout << "성공!" << endl;
                    }
    
                    //printVector(here);
    
                    reverse(here.begin() + i, here.begin() + j);
                }
            }
    
        }
    }
    
    
    int solve(const vector<int>& perm)
    {
        int n = perm.size();
        //vector<int> fixed(n, 0);
        vector<int> fixed(n);
    
    
        for(int i = 0; i < n; i++)
        {
            int smaller = 0;
    
            for(int j = 0; j < n; j++)
                if(perm[j] < perm[i])
                    smaller++;
    
            fixed[i] = smaller;
        }
    
        return dist[fixed];
    }
    
    
    
    int main()
    {
        for(int i=1; i<=8; i++)
            precalc(i);
    
    
        int tc;
        cin >> tc;
    
        while(tc--)
        {
            int n;
            cin >> n;
    
            vector<int> in;
    
    
            for(int i=0; i<n; i++)
            {
                int temp;
                cin >> temp;
                in.push_back(temp);
            }
    
    
            // 결과 출력
            cout << solve(in) << endl;
    
        }
    
        return 0;
    }
    


    11년 전
9개의 댓글이 있습니다.
  • Being
    Being

    어떤 환경에서 빌드하셨는지는 모르겠으나 최적화 옵션에 따른 차이가 매우 큰데요, 범인은 map<vector<int>, int>일 확률이 매우 높습니다.


    11년 전 link
  • Being
    Being

    제가 표준 라이브러리 구현체들의 컴파일 옵션에 따른 map<vector<int>, int>의 퍼포먼스에 대해 설명할 정도로 지식이 깊지는 않아서 전문가 찬스 쓰겠습니다. 아래 분이 대답해주실 거예요 :)


    11년 전 link
  • JongMan
    JongMan

    어떤 컴파일러를 쓰고 계신가요?


    11년 전 link
  • Signin
    Signin

    개발 환경은 Visual Studio 2010를 사용하고 있습니다!


    11년 전 link
  • xesmaster
    xesmaster

    디버그모드라 그런거같네여


    11년 전 link
  • Being
    Being

    아무튼 간에 map에 키를 컨테이너로 쓰는 건 빠르게 구현할 수는 있으나 내부에서 발생하는 각종 복사로 속도 측면에서 큰 페널티를 받게 됩니다. 궁금하시다면 키로 쓰이는 vector<int> 대신에 임의의 정수 값으로 대응시키는 함수를 작성해서 풀어 보시면 확실히 비교가 될 것 같네요.


    11년 전 link
  • Signin
    Signin

    xesmaster // 디버그 모드라면 한 step씩 실행시키는 모드 말씀이신가요?
    Being // 좋은 댓글 감사합니다. map의 구조상 오래 걸리게 되어있군요.


    11년 전 link
  • kcm1700
    kcm1700

    Signin // Debug 빌드가 있고 Release 빌드가 있습니다. Debug 빌드는 standard container를 사용할 경우 많이 느리지만, Release로 빌드할 경우 속도가 정상적으로 나옵니다.


    11년 전 link
  • Signin
    Signin

    kcm1700 // 그렇군요!! 빌드 옵션을 Release모드로 바꿨더니 속도가 정말 빨라졌네요... Debug 빌드라는 것을 처음 들었는데, 좋은 걸 배워갑니다^_^!!


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