CPP에서 구조체와 클래스 속도차이가 이렇게 많이 나나요?

  • bakbang
    bakbang

    안녕하세요 MORDOR 문제를 책에나와있는 RMQ 방법을 사용해 풀다가 질문드립니다.
    책에는 구조체로 구현되어있는데, '클래스로 구현해서 풀어볼까?'하는 생각에 아래와 같이 클래스로 구현해서 푸니까 5000ms제한시간에 시간초과가 나오더군요...
    그래서 그냥 책예제처럼 구조체로 구현해서 푸니까 348ms가 나왔네요.

    어떤 이유때문에 이렇게 차이가 날까요? 클래스는 구조체와 다르게 생성,소멸 과정에서 작동을 많이하나요? 코드를 읽고쓸준 알아도 언어가 내부적으로는 어떻게 동작하는지 잘 몰라서...ㅠ 질문드려봅니다.
    아시는분 알려주시면 감사하겠습니다~!!

    아래는 RMQ를 클래스로 구현한것입니다.

    #include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

#define INF 987654321

int TC,N,Q,a,b;
vector<int> mountain;

class RMQ {
    private:
        int n;
        vector<int> rangeMin;
    public:
        RMQ(vector<int> arr);
        int init(vector<int> arr,int left,int right,int node);
        int query(int left,int right,int node,int nodeLeft,int nodeRight);
        int query(int left,int right);
};
RMQ::RMQ(vector<int> arr)
{
    n=arr.size();
    rangeMin.resize(n*4);
    init(arr,0,n-1,1);
}
int RMQ::init(vector<int> arr,int left,int right,int node)
{
    if(left==right) return rangeMin[node]=arr[left];
    int mid=(left+right)/2;
    return rangeMin[node]=min(init(arr,left,mid,node*2),init(arr,mid+1,right,node*2+1));
}
int RMQ::query(int left,int right,int node,int nodeLeft,int nodeRight)
{
    if(right<nodeLeft || nodeRight<left) return INF;
    if(left<=nodeLeft && nodeRight<=right) return rangeMin[node];
    int mid=(nodeLeft+nodeRight)/2;
    return min(query(left,right,node*2,nodeLeft,mid),query(left,right,node*2+1,mid+1,nodeRight));
}
int RMQ::query(int left,int right){ return query(left,right,1,0,n-1);}

int main() {
    scanf("%d",&TC);
    while(TC--){
        scanf("%d %d",&N,&Q);
        mountain.clear();
        while(N--){
            scanf("%d",&a);
            mountain.push_back(a);
        }
        RMQ rmq_min(mountain);
        for(int i=0;i<mountain.size();++i) mountain[i]=-mountain[i];
        RMQ rmq_max(mountain);
        while(Q--){
            scanf("%d %d",&a,&b);
            int ret_min=rmq_min.query(a,b);
            int ret_max=rmq_max.query(a,b);
            cout<<-(ret_min+ret_max)<<endl;
        }
    }
}

    아래는 책에있는 RMQ를 구조체로 구현한것입니다. 알고스팟 책에있는 소스코드 있는 곳 에서 내려받은 코드의 주석지운겁니다. 보시면 알겠지만 내부코드 동작과정은 큰차이가 없습니다.

    #include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

#define INT_MAX 987654321

int TC,N,Q,a,b;
vector<int> mountain;
struct RMQ {
    int n;
    vector<int> rangeMin;
    RMQ(const vector<int>& array) {
        n = array.size();
        rangeMin.resize(n * 4);
        init(array, 1, 0, n-1);

    }
    int init(const vector<int>& array, int node, int left, int right) {
        if(left == right)
            return rangeMin[node] = array[left];
        int mid = (left + right) / 2;
        return rangeMin[node] = min(init(array, node*2, left, mid),
                                    init(array, node*2+1, mid+1, right));
    }
    int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
        if(index < nodeLeft || nodeRight < index) return rangeMin[node];
        if(nodeLeft == nodeRight) return rangeMin[node] = newValue;
        int mid = (nodeLeft + nodeRight) / 2;
        return rangeMin[node] = min(update(index, newValue, node*2, nodeLeft, mid),
                update(index, newValue, node*2+1, mid+1, nodeRight));
    }
    int update(int index, int newValue) { return update(index, newValue, 1, 0, n-1); }
    int query(int left, int right, int node, int nodeLeft, int nodeRight) {
        if(right < nodeLeft || nodeRight < left) return INT_MAX;
        if(left <= nodeLeft && nodeRight <= right) return rangeMin[node];
        int mid = (nodeLeft + nodeRight) / 2;
        return min(query(left, right, node*2, nodeLeft, mid),
                   query(left, right, node*2+1, mid+1, nodeRight));
    }
    int query(int left, int right) { return query(left, right, 1, 0, n-1); }
};
int main() {
    scanf("%d",&TC);
    while(TC--){
        scanf("%d %d",&N,&Q);
        mountain.clear();
        while(N--){
            scanf("%d",&a);
            mountain.push_back(a);
        }
        RMQ rmq_min(mountain);
        for(int i=0;i<mountain.size();++i) mountain[i]=-mountain[i];
        RMQ rmq_max(mountain);
        while(Q--){
            scanf("%d %d",&a,&b);
            int ret_min=rmq_min.query(a,b);
            int ret_max=rmq_max.query(a,b);
            cout<<-(ret_min+ret_max)<<endl;
        }
    }
}

    6년 전
2개의 댓글이 있습니다.
  • astein
    astein

    위에 적어주신 코드에서 제일 큰 차이점은

    RMQ(vector arr);
    int init(vector arr,int left,int right,int node);

    위의 두 함수입니다. 앞의 코드에서는 복사가 일어나고, 뒤의 코드에서는 그렇지 않은 점이 다릅니다. 저 부분만 수정하면 비슷한 시간에 통과될 것으로 보입니다.


    6년 전 link
  • bakbang
    bakbang

    아~ 주소로 전달을 안해서 arr가 복사가되었군요..! 못보고 지나갔는데 정말 비슷한 시간으로 통과되네요. 감사합니다!!


    6년 전 link

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