[C++/STL] Ranking System 분석

Ranking System 프로젝트 소개 및 구현내용

1-taek-gameprogramming.tistory.com/38

[C++/STL] Ranking System 소개 및 구현

---

프로젝트 분석

▶ 시퀀스 컨테이너 vs 연관 컨테이너

프로젝트의 주요 기능은 검색기능입니다. 연관컨테이너는 이진탐색트리구조로 되어 검색 기능의 특화되어있습니다. 시퀀스 컨테이너는 정렬된상태라면 이진탐색이 가능하여 빠른 검색이 가능합니다.

 

검색기능이 특화된 컨테이너를 찾아보자

컨테이너	Find
vector	정렬 O : O(log n) 정렬 X : O(n)
deque	정렬 O : O(log n) 정렬 X : O(n)
list / forward_list	O(n)
set / map	O(log n)
unordered set / unordered_map	O(1) or O(n)

unordered set과 unordered map은 hash를 사용하여 검색속도가 빠르지만, 정렬되어 있지않아 아래의 조건과 어울리지 않습니다.

• 내 등수, 상위 몇 %인가, 내 점수는 얼마인가를 표시한다.
• 내 순위 기준으로 내 위와 아래 순위 플레이어의 id와 점수를 표시한다.  

따라서 시퀀스 컨테이너 또한 정렬된 상태를 유지해야합니다.

 

로직에 의한 한계점

- 정렬된 vector/deque

vector와 deque은 스코어를 기준으로 정렬되어있습니다. 하지만 컨테이너의 value는 포인터(Player*)입니다. 이진탐색기능(equal_Range/ lower,upper_bound)을 사용할수없습니다. 따라서 순차검색을 통해 객체를 찾아야합니다.

 

- set/map

게임은 매 시즌 플레이어 점수가 변경됩니다. 그렇다면 map과 set은 트리의 모든 노드들의 구조를 변경되어야합니다. 따라서 매번 업데이트마다 업데이트 된 최신점수를 기준으로 새로운 map/set을 제작해야합니다.

 

그렇다면 chrono를 사용하여 시간을 측정해봅시다.

시퀀스 컨테이너(vector) 결과

대략 평균 60ms정도가 나옵니다.

연속 컨테이너(map) 결과

대략 평균 160ms 정도가 나옵니다.

 

결과분석

연속 컨테이너가 거의 두배이상의 시간이 소요되었습니다. 메모리 할당에 대한 오버헤드가 매우 심각한 영향을 미쳤습니다. 그럼으로 시퀀스 컨테이너를 사용해야합니다.

 

▶ Sequential access(순차 접근) vs Random access(비순차 접근)

랭킹시스템 로직에 의해 이진 탐색을 사용할수 없기 때문에, Sequential access구조와 Random access구조중 선별해내야합니다. 게임루프동안 갱신된 점수를 업데이트하기위해, 모든 플레이어들을 순회 해야합니다. Random access구조는 메모리가 연결되어있어 순회하는데 Sequential access보다 높은 성능을 보여줍니다.

출처: https://sites.google.com/site/waikenassignment2/sequential-and-random-access

 

▶ Random access - vector vs deque

chrono를 사용하여 시간 측정결과

vector

deque

vector는 평균 60ms, deque는 평균 100ms가 소요되었습니다.

 

deque의 메모리 구조

출처: http://cpp-tip-of-the-day.blogspot.com/2013/11/how-is-stddeque-implemented.html

deque은 vector와 array와는 다르게 모든데이터가 하나의 연속된 메모리에 올라가 있지 않습니다. 위 사진과 같이 byte단위의 chunk로 쪼개져 있습니다. 

 

결과분석

deque는 vector의 삽입/삭제시 메모리를 재할당하고 이전 객체들을 복사하는 단점을 보안한 컨테이너입니다. 위 랭킹시스템이 주로 다루고 있는 것은 빈번한 삽입삭제가 아닌 정해진 수의 플레이어들의 정보를 검색하는 것입니다. 따라서 제시된 증거로 인해 Ranking System Project의 가장 효율적인 컨테이너는 vector입니다.

 

▶ 프로젝트를 진행하며 느낀점

모든 컨테이너들 각자만의 고유한 장점들을 갖고있습니다. 불필요한 컨테이너는 존재하지 않으며, 주어진 로직에 따라 컨테이너들의 고유 장점들을 비교분석하여 효율적인 로직을 완성시켜야합니다. 랭킹시스템 프로젝트를 진행하며 선택한 컨테이너에 따라 프로젝트의 로직을 변경해야만 했고, 메모리구조와 알고리즘의 시간복잡도를 계산해가며 어떠한 컨테이너를 사용해야할지를 예측할 수 있었습니다.

 

+ 게임을 개발할때 오브젝트들을 관리하는 자원관리클래스를 구현해야하는데, 특정오브젝트를 찾기 위한 검색기능을 제공하기 위해, 그에 가장 적합한 컨테이너를 선택해야합니다. 검색기능의 특화된 컨테이너는 연관컨테이너지만, 자주 삽입삭제가 일어나는 게임오브젝트의 특성으로 인해, 트리의 재구성 혹은 해쉬의 재구성이 필요해집니다.

 

랭킹시스템 프로젝트 또한 매번 값이 업데이트, 수정되야한다는 동일한 특성을 갖고있습니다. 프로젝트 실험결과 vector가 가장 적합한 컨테이너로 선택되었고 게임오브젝트를 검색하는 기능을 제공하기 위한 컨테이너도 vector가 가장 적합하다는 근거를 제시할 수 있습니다.

---

프로젝트 출처

한국산업기술대학교 게임공학부 윤정현교수님 STL 수업 과제