개발하는 리프터 꽃게맨입니다.

GameObjectManager (가칭)전체 순회, 삽입, 삭제, 탐색 속도가 매우 빠른 컨테이너입니다.제목은 GameObjectManager 라고 지었는데, GameObject를 관리하기 위한 컨테이너 쯤으로 불러도 괜찮습니다.이름에서 볼 수 있듯 게임 오브젝트를 관리하기 위해서 만든 특별한 자료구조입니다.게임에서 가장 빈번히 일어나는 작업 중 하나는 컨터이너의 순회입니다. 보통 게임 오브젝트들은 매 틱마다 자신의 고유의 일을 수행하기 위해 Update 혹은 Tick 이라는 함수를 수행합니다. 그러기 위해서는 컨테이너에 수많은 오브젝트들을 저장하여 전체 순회를 통해서 상태를 갱신하는 설게를 사용할 수 있습니다. 그러므로 컨테이너의 순회는 1초에 최소 60번은 발생하며, 순회의 속도는 게임의 성능을 판가..

1. 오브젝트는 이중으로 관리 1) 빠른 삽입, 삭제, 탐색을 위한 해쉬 테이블 2) 빠른 순회를 위한 오브젝트 벡터, 빠른 삭제를 위해 특수한 형태의 벡터를 사용함 2. 해쉬 테이블 키 : 오브젝트의 ID (ID는 uint64 이며 유일하다.) 값 : std::pair (배열의 인덱스, 오브젝트의 unique_ptr) 3. 벡터 단순한 일자형 벡터 캐쉬 히트가 높아서 순회속도가 빠르다. 4. 탐색 해쉬 테이블을 통한 탐색 5. 삽입 해쉬 테이블을 통한 삽입 -> O(1) 배열에 추가적으로 삽입하고 배열의 인덱스를 해쉬 테이블에 업데이트 -> O(1) 이 때 push_back을 사용하면 안됨 벡터의 맨 뒤 인덱스를 얻어냄 해당 인덱스의 요소가 nullptr면 대입 해당 인덱스의 요소가 nullptr가 아..

#pragma oncenamespace MC{ template class Queue { public: Queue() : m_head(0), m_tail(0), m_count(0), m_capacity(1), m_data(1) {} void Push(T&& value) { if (m_count == m_capacity) { Reallocate(CapacityLogic()); } m_data[m_tail] = std::move(value); m_tail = (m_tail + 1) % m_capacity; m..

좋은 해쉬 함수가 뭔데? 자료구조에서의 해쉬 함수는 키 값을 이용해 해쉬 주소를 얻어낼 수 있는 함수를 뜻하며 이는 엄밀하게 정해져있는 것이 아니라, 프로그래머가 상황에 따라 재량껏 정의하여 사용합니다. 여기서 나쁜 해쉬 함수와 좋은 해쉬 함수는 엄연히 다릅니다. 좋은 해쉬함수가 되기위한 조건을 몇 가지 살펴보도록 하죠. 1) 좋은 해쉬 함수의 조건 (1) 해쉬 함수의 값이 해쉬 테이블 전체에 균일하게 분산되어야 한다. 해쉬에서는 키 값이 균일하게 분산되어 있을수록 좋습니다. 키 값이 균일하게 분산되다는 것이 곧 충돌이 적어짐을 뜻하죠. (2) 충돌 발생 빈도가 적어야 한다. (3) 연산이 빨라야 한다. 너무 연산량이 많은 해쉬의 경우에는 데이터 접근 속도가 느리기 때문에 좋은 해쉬함수라고 할 수 없습니..

선형조사법의 한계 closed hashing 인 선형조사법의 한계는 데이터 클러스터 현상입니다. 단순하게 말하면, 데이터가 한 곳에 몰려서 군집을 이룬다는 것이죠. 선형 조사법은 충돌 발생시 선형으로 빈공간을 탐색하기 때문에, 충돌이 발생한 지역 위주로 데이터가 몰릴 가능성이 높습니다. 이차조사법 및 이중해쉬는 closed hasing, open addressing 해쉬임과 동시에, 선형조사법의 클러스터 현상을 보완하는 해쉬 구조입니다. 이차조사법 1) 개요 이차조사법이 상당히 간단합니다. 그냥 선형조사법에 양념만 쳐주면 되죠. 이것이 선형조사법의 삽입 코드입니다. 충돌시 hashAddr +1, hashAddr +2, HashAddr +3... 이런 식으로 +1 씩 더해간다는 것을 알 수 있습니다. 이제..