[C++] STL 사용 시, 일반 반복문과 반복자 사용의 시간 차이

1822번: 차집합

위 문제를 풀면서 시간제한이라는 벽에 봉착하였다.
문제는 그냥 두 집합을 비교해서 A집합에만 있는 요소들을 추출해내는 것이다.

처음에는 O(N^2) 의 시간복잡도를 갖는 일반 2중 for 문으로 해결하려 하였으나...

input 값의 범위는 0 ~ 2147483647 인지라 시간초과가 안일어날 수가 없었다.

도저히 O(N^2) 밑으로 내릴 방법을 찾을 수가 없었는데, C++ 에도 Python 의 Dictionary 같은 것이 존재한다는 것을 알았다.

map STL

C++ 에서는 map 자료구조라고 하는데 vector 와는 내장함수가 유사하며, 기능은 Python 의 Dictionary 와 같다.

아무튼... 이 map 을 이용해서 O(N) 의 코드를 만들었는데

왜인지 시간초과가 뜬다???

int main(){
    scanf("%d %d",&nA,&nB);
    for(int i=0;i<nA;i++){
        int tmp;
        scanf("%d",&tmp);
        A[tmp]=1;
    }
    for(int i=0;i<nB;i++){
        int tmp;
        scanf("%d",&tmp);
        A[tmp]=0;
    }
    int cnt=0;
    for(int i=0;i<A.size();i++){
        if(A[i]==1)
            cnt+=1;
    }
    cout<<cnt<<"\n";
    for(int i=0;i<A.size();i++){
        if(A[i]==1)
            cout<<i<<" ";
    }
}

일단 이 로직에서 문제가 될 것은 마지막 map 을 다루는 for문이 분명했기에 반복자로 바꿔서 해보았다.
(참고로 map 은 bucket : [] 으로도 생성&삽입이 된다)

int main(){
    clock_t start,end;
    scanf("%d %d",&nA,&nB);
    for(int i=0;i<nA;i++){
        int tmp;
        scanf("%d",&tmp);
        A[tmp]=1;
    }
    for(int i=0;i<nB;i++){
        int tmp;
        scanf("%d",&tmp);
        A[tmp]=0;
    }
    int cnt=0;
    start=clock();
    for(auto it=A.begin();it!=A.end();it++){
        if(it->second==1)
             cnt+=1;
    }
    cout<<cnt<<"\n";
    for(auto it=A.begin();it!=A.end();it++){
        if(it->second==1)
            cout<<it->first<<" ";
    }
}

이 코드는 놀랍게도 같은 로직이지만 ...

통과가 된다.

그래서 STL 을 사용했을 때, 일반 for문 과 반복자를 이용한 for문 이 얼마나 차이가 있는지 궁금해졌다.

시간측정은 ctime 헤더에 있는 clock() 함수를 사용하였다.

start=clock();
for(auto it=A.begin();it!=A.end();it++){
    if(it->second==1)
        cnt+=1;
}
end=clock();

아까 반복자를 이용한 코드의 일부 for문 하나만 가져와서 측정하였다.

우선 2 밀리초 정도 걸린다.

start=clock();
for(int i=0;i<A.size();i++){
        if(A[i]==1)
        cnt+=1;
}
end=clock();

다음은 실패했던 코드이다. 측정해보자.

여러 번 해보았는데 같은 input 에 7 ~ 9 밀리초 정도 나온다.

추가적으로 더 많은 input 에도 해보았다.

미미하지만 차이가 더 벌어진 것을 확인할 수 있다.
아마 1822: 차집합 문제에서 최대 케이스가 2147483647 이고 최대개수는 500000 이므로

차이는 일반 for문과 반복자 for문에 따라 기하급수적으로 커질 것이다.

for 문들의 속도비교

위 stackoverflow 글을 첨언으로 넣자면, 같은 STL 내에서는 이왕이면 반복자를 쓰는게 더 빠른편이라고 한다.

아무튼 이제부터는 STL 순회할 때는 반복자를 쓰는 습관을 들이면 좋을 것 같다 :)