글 읽기 - c++ container에 대한 질문입니다 (정답코드 주의)

jcu011 4년 전 0

c++을 이용하여 풀었는데요

std::list

std::queue

위의 2가지 컨테이너를 이용하여 각각 제출하여 풀어봤습니다.

그런데 queue컨테이너를 사용하는것이 list컨테이너보다 훨씬 빠르더라구요.

C++ 레퍼런스를 보면 사용한 함수들의 시간복잡도는 다 constant라고 나와있는데

어디서 시간차이가 나는 걸까요...??

#include<bits/stdc++.h>
using namespace std;
// 4ms
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin>>n;
    //n--;
    queue<int> que;
    for(int i=1; i<=n; i++) que.push(i);
    
    while(que.size()!=1){
        que.pop();
        que.push(que.front());
        que.pop();
    }

    cout<<que.front();
}

/////////////////////////////////////////////////////////////////

//48ms
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin>>n;

    list<int> lst;
    for(int i=1; i<=n; i++) lst.push_back(i);
    n--;
    while(n--){
        lst.pop_front();
        lst.push_back(lst.front());
        lst.pop_front();
    }

    cout<<lst.front();

}

chogahui05 4년 전 1

말씀 주신 것은 캐시 히트와도 연관이 많아 보입니다.

queue가 array 기반으로 구현 되었다면 압살이고요.

2차 array (array + chunk) 기반으로 구현되어 있다면 expand가 덜 일어날 거에요. 대신에 로컬리티는 전자에 비해선 떨어집니다.. 만..

List보다는 나아요. 게다가.. List면 next나 prev와 같은 포인터도 따로 또 저장을 해야 합니다.

이는 locality 뿐만이 아니라 메모리 소모도 차이가 있을 거에요.

jcu011 4년 전 0

감사합니다.

두 컨테이너구조의 locality 차이로 인해 속도차이가 난다는 것은 이해했는데요.

expand가 일어난다는 것은 무슨뜻인가요 ?

그리고 캐시 히트와 연관이 있다는것은 데이터량이 커지게되면 list가 queue보다 빨라질 수도 있다는 뜻인가요 ??

chogahui05 4년 전 1

(1)

만약에 Queue가 deque 컨테이너 기반으로 설계되어 있고

deque가 2차 구조 (Chunk 포인터의 동적 배열)로 선언이 되어 있다고 생각해 봅시다.

우리는 Queue 구현체를 이것만 생각할 수 있는 건 아닙니다.

그냥 1차 구조 (배열에 item을 넣는. 우리가 흔히 알고 있는 rear와 front를 이용한 동적 배열)도 생각해 볼 수 있어요.

이 둘을 비교했을 때, 전자는 expand가 상대적으로 덜 일어납니다. 왜냐하면, chunk에 원소를 몇 개씩 때려 박아버리니까요.

실제로, 동적 배열이 가지고 있는 것은 chunk의 메모리 주소인데요. 예를 들어 chunk 하나당 256개의 int형을 저장할 수 있다고 합시다.

그리고 초기 size와 capacity가 각각 0, 4였다고 하면, item이 대충 1024개, 512개. 이 정도 들어갈 때 까지도 expand가 일어나지는 않을 거에요.

그런데 같은 size와 capacity를 1차 구조에서 가진 경우에, 4개 이상이 들어가면 expand가 일어날 수 밖에 없겠네요. (계속 push만 되었다면)

즉, 전자에 비해서는 후자 (1차 구조)가 expand 연산이 많이 일어날 수도 있겠거니. 라고 생각하시면 좋겠네요.

expand 연산이 일어난다는 것은 배열에 더 이상 push_back이나, push를 때려박을 수 없을 때

배열을 확장하는 연산을 의미합니다. 자료구조나 알고리즘 시간에 다루지 않았다고 하더라도 알아야 하는 개념이라고 생각합니다.

https://www.interviewcake.com/concept/java/dynamic-array

이 부분에 대한 개론은 이 사이트 참고 해 보세요. 특히 size와 capacity를 주목해서 보세요.

(2)

데이터량이 커지게되면 list가 queue보다 빨라질 수도 있다는 뜻인가요??

에 대한 답을 드리자면 queue가 어떻게 구현이 되었는지에 따라 다릅니다.

만약에 queue가 deque 기반으로 구현되었고, deque가 1차 구조로 구현 되었다. 그러면 잘 모르겠어요.

그런데 chunk의 동적 배열로 구현되었다. 그리고 queue의 배열을 써야 한다고 생각해 봅시다. 대략 30만개 정도의 multiqueue를 써야 한다고 생각해 볼까요?

그러면, 2차 구조로 구현된 deque 기반 queue라면.

기본적으로 1개를 넣었을 때 생기는 default 공간의 크기가 커요. 기본적인 공간이 크게 잡힌다는 것은 오버헤드가 상당히 클 수도 있다는 의미입니다.

예를 들자면, 한 원소당 512byte의 크기를 가지는, 30만개의 원소를 저장하는 배열과

한 원소당 4byte의 크기를 가지는, 30만개의 원소를 저장하는 배열이 있다고 생각해 봅시다.

어떤 게 로컬리티가 좋을까요..? 라고 물어보신다면. 음.. 후자 아닐까요?

애초에 List는 띄엄 띄엄 저장이 되어 있기에

배열보다 기본적으로는 locality가 좋지 않은 것은 맞습니다. 맞는데..

기본 default가 4, 8byte 정도밖에 안 되는 원소를 리스트로 이어버린 거나.

한 개당 512byte짜리를, 한 30만개 정도를, 그냥 배열에 때려 박은 거랑은 어떻게 비교를 하면 좋을까요? 단지 배열이 로컬리티가 좋다. 로 비교하면 좋을까요?

아니면 배열이긴 한데 덩치가 커서 로컬리티가 떨어질 수 있다. 로 결론을 내리는 게 좋을까요?

chogahui05 4년 전 1

이것과 비슷한 질문일지도 모르겠습니다만..

참고하셔도 좋을 듯 싶어요.

https://www.acmicpc.net/board/view/46709#comment-80462

https://www.acmicpc.net/board/view/36399#comment-64810

jcu011 4년 전 0

자세한 답변 정말 감사드립니다.

많은 도움되었습니다 ...!!!

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

문제

문제

출처

ICPC

c++ container에 대한 질문입니다 (정답코드 주의)

jcu011 4년 전 0

chogahui05 4년 전 1

jcu011 4년 전 0

chogahui05 4년 전 1

chogahui05 4년 전 1

jcu011 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말