실행시간과 메모리 용량과 같은 자원을 최소로 사용하면서 최대의 효율을 뽑아내기 위해 필수 요소인 자료구조에 대해서 공부하다가 문득 map과 set이 떠올랐다. 비슷한 associative array인데, 이 두개에 대한 차이점이 항상 깊게 와닿지 않아서 작성하게 되었다.
array
array의 단점은, 항목을 추가하거나 제거할 때 비용이 많이 든다는 것이다. 플레이어가 걸을 때 고정된 수의 발자국을 표시할 때, 혹 경기장에 고정된 크기의 2D 그리드. 유닛이 취할 수 있는 특정 경로들을 array에 추가하면 좋겠다.
list
반복하고 싶은 항목이 여러개 있을 때, 인덱스를 통하여 특정 항목에 액세스해야할 때 예시로는 현재 활성되어 있는 유닛, 장면에 있는 모든 적의 목록, 특정 상태의 모든 유닛 목록들을 list로 사용하면 되겠다.
dictionary
다른 개체를 기반으로 관련된 개체를 빠르게 가져와야 할 때, 모든 항목을 반복할 필요가 없고, 항목에 추가 제거가 빈번하게 일어날 때 실제 예시로는 x,y값을 기반으로 위치 정보를 찾고 점유되어 있는지 확인할 때에는 dictionary를 사용하는것이 좋다. 문자열을 기반으로 스프라이트 이미지를 찾을 때 등..
map
map이란 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열로, key와 value의 쌍으로 이루어진 트리이다. 검색, 삽입, 삭제의 속도가 빠르고, 검색 속도가 빠른데 그 이유는 key를 기준으로 정렬된 상태이기 때문이다.
map도 iterator를 사용할 수 있고, key(index)로 이용할 수 있다. 맵에 원소 쌍을 추가하는 방법은 insert로도 가능하고, key와 value를 값으로 받아 map[key] = value로 map에 추가할 수 있다.
unordered_map
map은 기본적으로 정렬이 된 상태를 유지하기 때문에 데이터가 크면 연산의 시간이 길어질 수 있다. 따라서 문제에 따라 unordered_map이 사용될 때가 있다.
데이터 양이 많은 경우 map보다 unordered_map이 성능이 더 좋고, unordered_map은 hash_table 기반의 해시 컨테이너로 데이터가 적을 땐 map이 성능이 더 좋지만 이 외의 상황에서는 일관된 성능으로 unordered_map이 map보다 더 효율이 좋다.
hash table
우리가 모바일 게임을 할 때, UserKey가 엄청 수 많은 영어와 숫자로 이루어진 것을 볼 수 있다. 이 것과 같이 게임에 입장할 때 RoomName등, 다양한 UserId와 Time을 더해서 발급하는 유저의 고유한 값을 만들어줄 수 있고, 값으로 일일히 검색하여야하는 경우 큰 효율을 얻을 수 있다. Dictionary 도 또한 hash를 사용하여 빠른 속도를 보여주는데, 유니티 3D C#에서는 해쉬테이블보다 dictionary를 많이 사용한다고 한다. 그 이유는 hash table의 경우는 인자를 넣지 않아도 자동으로 타입을 유추해주는데, 이 것에 대한 비용이 비싸지만 dictionary는 타입을 직접 정해놓고 가기 때문에 비용이 비교적 싸고 유연하다고 한다.
set
set은 key만 있는 map, 혹 정렬된 집합이라고 생각하면 쉽게 이해할 수 있다.
사용법도 map과 크게 다르지 않고, 정렬된 집합이라고 정의한 이유는 set이 가지는 값들이 중복을 허락하지 않고 정렬되어 있기 때문이다. 사용되는 용도는 특정 값에 대해 검색을 할 때 사용하게 된다.
다양한 자료구조, map과 set 차이
실행시간과 메모리 용량과 같은 자원을 최소로 사용하면서 최대의 효율을 뽑아내기 위해 필수 요소인 자료구조에 대해서 공부하다가 문득 map과 set이 떠올랐다. 비슷한 associative array인데, 이 두개에 대한 차이점이 항상 깊게 와닿지 않아서 작성하게 되었다.
array
array의 단점은, 항목을 추가하거나 제거할 때 비용이 많이 든다는 것이다. 플레이어가 걸을 때 고정된 수의 발자국을 표시할 때, 혹 경기장에 고정된 크기의 2D 그리드. 유닛이 취할 수 있는 특정 경로들을 array에 추가하면 좋겠다.
list
반복하고 싶은 항목이 여러개 있을 때, 인덱스를 통하여 특정 항목에 액세스해야할 때 예시로는 현재 활성되어 있는 유닛, 장면에 있는 모든 적의 목록, 특정 상태의 모든 유닛 목록들을 list로 사용하면 되겠다.
dictionary
다른 개체를 기반으로 관련된 개체를 빠르게 가져와야 할 때, 모든 항목을 반복할 필요가 없고, 항목에 추가 제거가 빈번하게 일어날 때 실제 예시로는 x,y값을 기반으로 위치 정보를 찾고 점유되어 있는지 확인할 때에는 dictionary를 사용하는것이 좋다. 문자열을 기반으로 스프라이트 이미지를 찾을 때 등..
map
map이란 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열로, key와 value의 쌍으로 이루어진 트리이다. 검색, 삽입, 삭제의 속도가 빠르고, 검색 속도가 빠른데 그 이유는 key를 기준으로 정렬된 상태이기 때문이다.
map도 iterator를 사용할 수 있고, key(index)로 이용할 수 있다. 맵에 원소 쌍을 추가하는 방법은 insert로도 가능하고, key와 value를 값으로 받아 map[key] = value로 map에 추가할 수 있다.
unordered_map
map은 기본적으로 정렬이 된 상태를 유지하기 때문에 데이터가 크면 연산의 시간이 길어질 수 있다. 따라서 문제에 따라 unordered_map이 사용될 때가 있다.
데이터 양이 많은 경우 map보다 unordered_map이 성능이 더 좋고, unordered_map은 hash_table 기반의 해시 컨테이너로 데이터가 적을 땐 map이 성능이 더 좋지만 이 외의 상황에서는 일관된 성능으로 unordered_map이 map보다 더 효율이 좋다.
hash table
우리가 모바일 게임을 할 때, UserKey가 엄청 수 많은 영어와 숫자로 이루어진 것을 볼 수 있다. 이 것과 같이 게임에 입장할 때 RoomName등, 다양한 UserId와 Time을 더해서 발급하는 유저의 고유한 값을 만들어줄 수 있고, 값으로 일일히 검색하여야하는 경우 큰 효율을 얻을 수 있다. Dictionary 도 또한 hash를 사용하여 빠른 속도를 보여주는데, 유니티 3D C#에서는 해쉬테이블보다 dictionary를 많이 사용한다고 한다. 그 이유는 hash table의 경우는 인자를 넣지 않아도 자동으로 타입을 유추해주는데, 이 것에 대한 비용이 비싸지만 dictionary는 타입을 직접 정해놓고 가기 때문에 비용이 비교적 싸고 유연하다고 한다.
set
set은 key만 있는 map, 혹 정렬된 집합이라고 생각하면 쉽게 이해할 수 있다. 사용법도 map과 크게 다르지 않고, 정렬된 집합이라고 정의한 이유는 set이 가지는 값들이 중복을 허락하지 않고 정렬되어 있기 때문이다. 사용되는 용도는 특정 값에 대해 검색을 할 때 사용하게 된다.
@